【提取素因子+积性函数】小明的密钥
http://acm.nyist.net/JudgeOnline/problem.php?pid=362
http://dl.iteye.com/upload/attachment/542389/ef4eeb1f-753e-3a13-b420-ca4efce4e2a7.png
#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 M1005LL prime;bool mark;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){prime = i;for (j = i << 1; j < M; j += i)if (!mark)mark = true;}}while (~scanf ("%lld%lld", &a, &b)){ans = 1;for (i = 0; i < k; i++){if (sqrt(1.0*a) < prime)break;if (a % prime == 0){tp = 0;//tp相当于x2while (a % prime == 0)a /= prime, 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;}
页:
[1]