pku1845.java

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define Prime 9901

int Mod(int x, int n)
{
	int ans;
	if (n == 0)
	{
		return 1;
	}
	ans = Mod(x, n / 2);
	ans = ans * ans % Prime;
	if (n % 2)
	{
		ans = ans * x % Prime;
	}
	return ans;
}

int Calc(int A, int B)
{
	int i, j, k, ans1, ans2, tmp;
	int value[10], count[10], cnt;
	cnt = 0;
	
	if (B == 0 || A == 1)
	{
		return 1;
	}
	
	for (i = 2; i * i <= A; i++)
	{
		if (A % i == 0)
		{
			count[cnt] = 0;
			value[cnt] = i;
			do
			{
				A /= i;
				count[cnt]++;
			}
			while (A % i == 0);
			cnt++;
		}
	}
	if (A > 1)
	{
		value[cnt] = A;
		count[cnt] = 1;
		cnt++;
	}
	for (i = 0, ans1 = 1, ans2 = 1; i < cnt; i++)
	{
		if (value[i] % Prime == 0)
		{
			continue;
		}
		if (value[i] % Prime == 1)
		{
			ans1 *= (B * count[i] + 1);
			ans1 %= Prime;
			continue;
		}
		if (value[i] == Prime)
		{
			continue;
		}
		if (value[i] % Prime == 1)
		{
			ans1 = ans1 * (B * count[i] + 1) % Prime;
			continue;
		}
		tmp = Mod(value[i] % Prime, B * count[i] + 1);
		tmp = (tmp + Prime - 1) % Prime;
		ans1 = tmp * ans1 % Prime;
		ans2 = ans2 * (value[i] + Prime - 1) % Prime;
	}
	for (i = 0; i < Prime; i++)
	{
		if (ans1 == ans2 * i % Prime)
		{
			break;
		}
	}
	return i;
}

int main()
{
	int A, B;
	while (scanf("%d%d", &A, &B) != -1)
	{
		printf("%d\n", Calc(A, B));
	}
	return 0;
}