【提取素因子+积性函数】小明的密钥

 

 http://acm.nyist.net/JudgeOnline/problem.php?pid=362

 

 

 

 

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL long long
#define inf 0x3fffffff
#define M  1005

LL prime[170];
bool mark[M];

LL f (LL n)    //自然数立方和公式，边乘边模
{
	return (n * (n+1) / 2) % 10007 * (n * (n+1) / 2) % 10007;
}

int main()
{
	LL i, j, k = 0, a, b, tp, cc = 1, ans;
	for (i = 2; i < M; i++)		//打1005以内素数就够了
	{
		if (!mark[i])
		{
			prime[k++] = i;
			for (j = i << 1; j < M; j += i)
				if (!mark[j])
					mark[j] = true;
		}
	}
	while (~scanf ("%lld%lld", &a, &b))
	{
		ans = 1;
		for (i = 0; i < k; i++)
		{
			if (sqrt(1.0*a) < prime[i])
				break;
			if (a % prime[i] == 0)
			{
				tp = 0;						//tp相当于x2
				while (a % prime[i] == 0)
					a /= prime[i], tp++;
				tp = tp * b + 1;			//相当于x2*b+1
				ans = ans * f(tp) % 10007;	//边模边乘
			}
			if (a == 1)
				break;
		}
		if (a > 1)		//注意可能存在>sqrt(a)的素因子
		{
			tp = b + 1;
			ans = ans * f(tp) % 10007;
		}
		printf ("Case %lld: %lld\n", cc++, ans);
	}
    return 0;
}