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

?

?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  1005LL 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相当于x2while (a % prime[i] == 0)a /= prime[i], tp++;tp = tp * b + 1;//相当于x2*b+1ans = 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;}

??