3067558_ole.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;
	}
}

void OLE()
{
	while (true)
	{
		puts("Bless Sql");
	}
}

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

	scanf("%I64d%I64d",&a,&b);
	if (a==0)
	{
		if (b==0)
		{
			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++;
	}
	for(i = 3; i < a; i+=2)
	{
		if(a%i==0)
		{
			num[m] = i;
			while(a%i==0)
			{
				a /= i;
				cnt[m]++;
			}
			cnt[m] *= b;
			m++;
		}
	}
	if(a!=1)
	{
		num[m] = a;
		cnt[m] = b;
		m++;
	}
	__int64 ans = 1;
	for(i = 0; i < m; i++)
	{
		__int64 tmp;
		if((num[i]-1)%9901!=0)
		{
			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;
			
		}
		else
		{
			if (cnt[i]!=1)
			{
				OLE();
			}
			tmp = num[i]+1;
		}
		tmp %= 9901;
		ans *= tmp;
		ans %= 9901;
	}
	printf("%I64d\n",ans%9901);
	return 0;
}