数学专题习题2

题目传送门

Code

//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;
}