【题目地址】 http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1951【题目大意】 PS.此题的题目描述是 亮点,膜拜ipig~ “在那山的那边海的那边有一群小肥猪。他们活泼又聪明,他们调皮又灵敏。他们自由自在生活在那绿色的大草坪,他们善良勇敢相互都关心……” ——选自猪王国民歌 给出N,G 求 G^( sigma(C(N,i) ) % P i 满足 i | N P = 999911659
【解题思路】 1. P 为素数 2. Phi(P) = P - 1 为square - free 数 3. 由于mod P,并且P 为素数,于是可以将指数直接mod Phi(P), 利用的是mod 素数的指数循环节开始位置必然为0 (具体见本人以前的文章)
于是问题就转化为组合数 由于N 比较小 (N <= 10 ^9)于是可以分别计算 c(N,i) % Pi Pi 为 P - 1 的因子,容易知道 max{Pi} 很小 于是可以利用lucas定理求解 得到结果以后使用中国剩余定理合并即可(CRT)
于是问题就完美解决了,不过本人写的比较疵,且第一次提交忘记了一个可能溢出的细节,于是2Y,并跑了700+ MS....(卡过~)
【程序代码】
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<cmath> 5 #include<map> 6 #include<string> 7 #include<algorithm> 8 #include<vector> 9 10 using namespace std; 11 12 typedef long long LL; 13 14 const int maxn = 36000; 15 int f[4][maxn]; 16 17 int b[5] = {0,0,0,0}; 18 int w[5] = {2,3,4679,35617}; 19 const int P = 999911659; 20 int N,G; 21 22 int ext_gcd(int a, int b, int &x, int &y) { 23 int t, d; 24 if (! b) { x = 1; y = 0; return a; } 25 d = ext_gcd(b, a % b, x, y); 26 t = x; 27 x = y; 28 y = t - a / b*y; 29 return d; 30 } 31 int China(int b[], int w[], int k) { 32 int i; 33 int d, x, y, m, n = 1; 34 LL a = 0; 35 for (i = 0; i < k; i++) n *= w[i]; 36 for (i = 0; i < k; i++) { 37 m = n / w[i]; 38 d = ext_gcd(w[i], m, x, y); 39 a = (a + (LL)y * m * b[i]) % n; 40 } 41 if (a > 0) return a; 42 return (a + n); 43 } 44 45 int s[2][101]; 46 47 int powmod(LL a,int b,int c) { 48 LL ret = 1; 49 while(b) { 50 if(b & 0x1) ret = ret * a % c; 51 a = a * a % c; 52 b >>= 1; 53 } 54 return ret; 55 } 56 int cnk(int n,int k,int cur) { 57 int ans = f[cur][n],p = w[cur]; 58 ans = ans * powmod(f[cur][k],p - 2, p) % p; 59 ans = ans * powmod(f[cur][n - k],p - 2, p) % p; 60 return ans; 61 } 62 63 int C(int n,int k,int cur) { 64 int i,x,len[2] = {0,0},c = 0,p = w[cur]; 65 x = n; 66 while(x) s[0][len[0] ++] = x % p,x /= p; 67 x = k; 68 while(x) s[1][len[1] ++] = x % p, x/= p; 69 while(len[1] < len[0]) s[1][len[1] ++] = 0; 70 for(i = 0; i < len[0]; ++ i) if(s[1][i] > s[0][i]) return 0; 71 int ans = 1; 72 for(i = 0; i < len[0]; ++ i) ans = ans * cnk(s[0][i],s[1][i],cur) % p; 73 return ans; 74 } 75 76 int main() { 77 int i,j; 78 for(i = 0; i < 4; ++ i) { 79 f[i][0] = 1; 80 for(j = 1; j < w[i]; ++ j) 81 f[i][j] = f[i][j - 1] * j % w[i]; 82 } 83 scanf("%d%d",&N,&G); 84 if(G == P) { 85 puts("0"); 86 return 0; 87 } 88 G %= P; 89 for(i = 1; i * i <= N; ++ i) 90 if(N % i == 0) { 91 int x = i; 92 b[0] = (b[0] + C(N,x,0)) % w[0]; 93 b[1] = (b[1] + C(N,x,1)) % w[1]; 94 b[2] = (b[2] + C(N,x,2)) % w[2]; 95 b[3] = (b[3] + C(N,x,3)) % w[3]; 96 x = N / i; 97 if(i * i != N) { 98 b[0] = (b[0] + C(N,x,0)) % w[0]; 99 b[1] = (b[1] + C(N,x,1)) % w[1]; 100 b[2] = (b[2] + C(N,x,2)) % w[2]; 101 b[3] = (b[3] + C(N,x,3)) % w[3]; 102 } 103 } 104 int ans = powmod(G,China(b,w,4),P); 105 printf("%d\n",ans); 106 return 0; 107 }
|