//UVA-11728
#include<bits/stdc++.h>
using namespace std;

int kase = 0,S;
bool check(int n,int m)
{
	int q = sqrt(n+0.5);
	int ret = 0;
	for (int i = 1; i <= q; i++)
	if (n % i == 0)  ret += i+n/i;
	if (q*q == n) ret -= q;
	return (ret == m);
}
int main(int argc, char *argv[])
{
	while(scanf("%d",&S) == 1 && S)
	{
		bool flag = 0;
		if (S == 1)
		{
			printf("Case %d: 1\n",++kase);
			continue;
		}
		for (int i = S-1; i >= 1; i--)
			if (check(i,S))
			{
				flag = 1;
				printf("Case %d: %d\n",++kase,i);
				break;	
			}
		if(!flag) printf("Case %d: %d\n",++kase,-1);	
	}
	return 0;
}

// UVA-10673
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline void getLL(LL &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}

void ex_gcd(LL a,LL b,LL &X,LL &Y,LL &d)
{
	if (!b){d=a;X=1;Y=0;}
	else
	{
		ex_gcd(b,a%b,Y,X,d);
		Y-=(a/b)*X;
	}
}

LL T,x,k,a,b,X,Y,d;

int main(int argc, char *argv[])
{
	getLL(T);
	while(T--)
	{
		getLL(x);getLL(k);
		a = floor(double(x)/double(k));
		b = ceil(double(x)/double(k));
		d = a == b ? a : 1;
		if (a == b)
			X = 0,Y = k;
		else
		{
			ex_gcd(a,b,X,Y,d);
			X *= x, Y *= x;
		}
		printf("%lld %lld\n",X,Y);
	}
	return 0;
}

//UVA-11768
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll& g,ll& x,ll& y)
{
    if(!b) g=a,x=1,y=0;
    else exgcd(b,a%b,g,y,x),y-=x*(a/b);
}
double X1,Y1,X2,Y2;
ll solve()
{
    ll x1=(X1+0.05)*10,y1=(Y1+0.05)*10,x2=(X2+0.05)*10,y2=(Y2+0.05)*10;
    if(x1==x2) {
        if(x1%10) return 0;
        if(Y2<Y1) swap(Y1,Y2);
        return floor(Y2)-ceil(Y1)+1;
    }
    if(y1==y2) {
        if(y1%10) return 0;
        if(X2<X1) swap(X1,X2);
        return floor(X2)-ceil(X1)+1;
    }
    ll a=(y2-y1)*10,b=(x1-x2)*10,c=y2*x1-y1*x2,g,x,y;
    exgcd(a,b,g,x,y);
    if(c%g) return 0;
    x*=c/g;b=abs(b/g);
    if(X1>X2) swap(X1,X2);
    x1=ceil(X1);x2=floor(X2);x-=(x-x1)/b*b;
    if(x<x1) x+=b;
    if(x2<x) return 0;
    return (x2-x)/b+1;
}

int main(int argc, char *argv[])
{
    int T;
    scanf("%d",&T);
    while(T--) 
	{
        scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
        printf("%lld\n",solve());
    }
    return 0;
}

//UVA-10692
#include<bits/stdc++.h>
const int maxn = 15;
int A[maxn], k;
int pow_mod(int a, int n, int M) 
{
    int ans = 1;
    while (n) {
        if (n&1)
            ans = ans * a % M;
        a = a * a % M;
        n /= 2;
    }
    return ans;
}

int euler_phi(int n)
{
    int m = (int)sqrt(n+0.5);
    int ans = n;
    for (int i = 2; i <= m; i++) {
        if (n % i == 0) {
            ans = ans / i * (i-1);
            while (n%i==0)
                n /= i;
        }
    }

    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

int solve (int d, int M) 
{
    if (d == k - 1)
        return A[d]%M;
    int phi = euler_phi(M);
        int c = solve (d+1, phi) + phi;
    return pow_mod(A[d], c, M);
}

int main (int argc, char *argv[]) 
{
    int cas = 1;
    char str[maxn];

    while (scanf("%s", str) == 1 && strcmp(str, "#")) 
	{
        int M;
        sscanf(str, "%d", &M);
        scanf("%d", &k);
        for (int i = 0; i < k; i++)
            scanf("%d", &A[i]);
        printf("Case #%d: %d\n", cas++, solve(0, M));
    }
    return 0;
}

数学专题习题

发表于 2018-02-15 | 分类于数学

字数统计: 1,098字 | 阅读时长 ≈ 7分钟

题目传送门

UVa-10237
UVa-10883
UVa-10943
UVa-11038
UVa-11076
UVa-11388
UVa-11889

Code

//UVA-10237
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 40;

int n, k;
ll b[N][N*N],w[N][N*N];

void init() 
{
    memset(b, 0, sizeof(b));
    memset(w, 0, sizeof(w));
    b[0][0] = w[1][0] = 1;
    for (int i = 1; i <= n; i++) 
	{
        b[i][0] = b[i-1][0];

        int l = (i+1)/2 * 2 - 1;
        for (int j = 1; j <= l && j <= k; j++)
            b[i][j] = b[i-1][j] + (ll)(l-j+1) * b[i-1][j-1];
    }

    for (int i = 2; i <= n; i++) 
	{
        w[i][0] = w[i-1][0];

        int l = i/2 * 2;
        for (int j = 1; j <= l && j <= k; j++)
            w[i][j] = w[i-1][j] + (ll)(l-j+1) * w[i-1][j-1];
    }
}

int main (int argc, char *argv[]) 
{
    while (scanf("%d%d", &n, &k) == 2 && n + k)
	{
        init();
        ll ans = 0;
        for (int i = 0; i <= k; i++)
            ans = ans + b[n][i] * w[n][k-i];
        printf("%lld\n", ans);
    }
    return 0;
}

//UVA-10883
#include<bits/stdc++.h>
using namespace std;
int T,n,kase = 0;
double ln[50010],a;
void init(void)
{
	ln[0] = ln[1] = 0;
	for (int i = 2; i <= 50009; i++)
	ln[i] = ln[i-1]+log(i);
}
int main(int argc, char *argv[])
{
	init();
	cin >> T;
	while(T--)
	{
		cin >> n;
		n--;
		double summ = 0.0;
		for (int i = 0; i <= n; i++)
		{
			cin >> a;
			summ += a * exp(ln[n]-ln[n-i]-ln[i]-n*ln[2]);
		}
		printf("Case #%d: %.3lf\n",++kase,summ);
	}
	return 0;
}

//UVA-10943
#include<bits/stdc++.h>
using namespace std;
int N,K;
int C[210][210];
const int module = 1e6;
void in_table(void)
{
	for (int i = 0; i <= 208; i++)
		for (int j = 0; j <= i; j++)
		{
			if (i == j)  C[i][j] = 1;
			else C[i][j] = (C[i-1][j-1]+C[i-1][j])%module;	
		} 
}
int main(int argc, char *argv[])
{
	in_table();
	while(scanf("%d %d",&N,&K) == 2 && N && K)
	{printf("%d\n",C[N+K-1][K-1]);}
	return 0;
}

//UVA-11038
#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n;
int f[13],g[13]; //10^i~10^(i+1)-1
int calc(int x)
{
	int ans=1,cnt=1,tmp=0;
	if (x < 0)
	return 0;
	while(x)
	{
		int c = x%10;
		x/=10;
		if (c) ans+=x*cnt;
		else ans+=(x-1)*cnt+tmp+1;
		tmp+=c*cnt;
		cnt*=10;
	}
	return ans;
}
signed main(signed argc, char *argv[])
{
	f[0] = g[0] = 1;
	for (int i = 1; i <= 11; i++)
	f[i] = (9*(i-1))*i+i;
	for (int i = 1; i <= 11; i++) g[i] = g[i-1]+f[i];
	while(scanf("%lld%lld",&n,&m) == 2 && n >= 0 && m >= 0)
		printf("%lld\n",calc(m)-calc(n-1));
	return 0;
}

//UVA-11076
#include<bits/stdc++.h>
using namespace std;
int n,a[13],c[11],d[11];
unsigned long long ans,t = 1;
unsigned long long op(int x)
{
	unsigned long long ret = 1;
	int y=x;
	while(y) ret*=y,y--;
	return ret;
}
unsigned long long op1(int x)
{
	unsigned long long ret = 0;
	while(x)
	{
		x--;
		ret+=pow(10,x);
	}
	return ret;
}
int main(int argc, char *argv[])
{
	while(scanf("%d",&n) == 1 && n)	
	{
		memset(c,0,sizeof(c));
		for (int i = 1; i <= n; i++) scanf("%d",&a[i]),c[a[i]]++;
		unsigned long long f = op(n),mul = op1(n);
		for (int i = 0; i <= 9; i++) f/=(op(c[i]));
		for (int i = 0; i <= 9; i++) d[i] = f*c[i]/n;
		ans = 0;
		for (int i = 0; i <= 9; i++) ans += d[i]*i*mul;
		cout << ans << endl;
	} 
	return 0;
}

//UVA-11388
#include<bits/stdc++.h>
using namespace std;
int T;
#define LL long long
long long gcd(long long x,long long y)
{
 	return (y == 0) ? x : gcd(y,x%y);
}
int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);
	long long T,G,L;
	cin >> T;
	while(T--)
	{
		int flag = 0;
		cin >> G >> L;
		if (L % G != 0) 
		{
			cout << "-1" << endl;
			continue;
		}
		else
		{
			cout << G << " " << L << "\n";
			continue;
		}
		/*
		long long x = G*L;
		for (long long i = G; i <= min((LL)sqrt(x),L); i++)
		{
			if (x % i == 0)
			{
				if (gcd(i,x/i) == G)
				{
					printf("%lld %lld\n",i,x/i);
					flag = 1;
					break;
				}
			}
		}
		if (!flag) printf("-1\n");*/
	}
	
	return 0;
}

//UVA-11889
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long gcd(long long x,long long y)
{
 	return (y == 0) ? x : gcd(y,x%y);
}
signed main(signed argc, char *argv[])
{
	int A,C,T;
	ios::sync_with_stdio(false); 
	cin >> T;
	while(T--)
	{
		int flag = 1;
		cin >> A >> C;
		for (int i = 1; i <= A; i++)
			if (i*C % A == 0)
			{
				int B = i * C/A;
				if (gcd(A,B) == i) 
				{
					printf("%d\n",B);
					flag = 0;
					break;
				}
			}
		if (flag) puts("NO SOLUTION");
	}
	return 0;
}

[LA-3485] Bridge 基于定积分的二分

发表于 2018-02-13 | 分类于数学

字数统计: 916字 | 阅读时长 ≈ 5分钟

题面

传送门:LA-3485
题目大意:给定一个抛物线的左右长度和曲线长，求抛物线的底到顶部的距离。

阅读全文 »