3067471_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>

__int64 num[1000];
__int64  cnt[1000];

__int64 power(__int64 p,__int64 n)
{
	if (n==1)
	{
		return p%9901;
	}
	if (n%2==0)
	{
		__int64 t = (p*p)%9901;
		p = t;
		return power(p,n/2)%9901;
	}
	else
	{
		return ((p%9901)*power(p,n-1))%9901;
	}
}

int main()
{
	int a, b, m, i;
	__int64 j;

	__int64 nn = 50000000;
	nn *= nn;
	printf("%I64d\n",nn);
	scanf("%d%d",&a,&b);
	if (a==0)
	{
		if (b==1)
		{
			puts("1");
		}
		else
		{
			puts("0");
		}
		return 0;
	}
	if (a==1||b==0)
	{
		puts("1");
		return 0;
	}
	m = 0;
	memset(cnt,0,sizeof(cnt));
    if(a%2==0)
	{
		num[m] = 2;
        while(a%2==0)
        {
			a /= 2;
            cnt[m]++;
		}
		cnt[m] *= b;
        m++;
	}
	//t = (int)sqrt(a)+1;
    for(i = 3; i < a&&a!=1; i+=2)
	{
		if(a%i==0)
		{
			num[m] = i;
            while(a%i==0)
			{
				a /= i;
                cnt[m]++;
			}
			cnt[m] *= b;
            //t = (int)sqrt(a)+1;
            m++;
		}
	}
	if(a!=1)
	{
		num[m] = a;
        cnt[m] = b;
        m++;
	}
	__int64 ans = 1;
    for(i = 0; i < m; i++)
    {
		//printf("%I64d %I64d\n",num[i],cnt[i]);
		__int64 tmp = (power(num[i],cnt[i]+1)+9900)%9901;
        for(j = 1; j < 9901; j++)
		{
			if(j*(num[i]-1)%9901==1)
				break;
		}
		tmp *= j;
        tmp %= 9901;
        ans *= tmp;
        ans %= 9901;
	}
	printf("%I64d\n",ans);
	return 0;
}