首页 > 代码库 > BZOJ1951 [Sdoi2010]古代猪文
BZOJ1951 [Sdoi2010]古代猪文
这道题是各种数论搞在一起的题目。。。
首先由burnside引理可以知道答案是ans = (G^sigma(C(n, d))) % MOD
然后由费马小定理，ans = (G^（sigma(C(n, d)) % (MOD - 1)）) % MOD
之后把MOD - 1分解为2 * 3 * 4679 * 35617，用Lucas定理分别求出sigma(C(n, d)) % m，其中m = 2, 3, 4679, 35617
最后再用中国剩余定理合起来快速幂一下就好辣！
1 /************************************************************** 2 Problem: 1951 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:76 ms 7 Memory:2772 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 13 using namespace std;14 typedef long long LL;15 const LL p = 999911659;16 const int x[4] = {2, 3, 4679, 35617};17 18 LL mod[4][50000], a[50000], b[5], cnt, n, g, y, z;19 20 inline LL pow(LL a, LL b, LL p){21 LL res = 1;22 while (b){23 if (b & 1) res *= a, res %= p;24 a *= a, a %= p;25 b >>= 1;26 }27 return res;28 }29 30 LL extend_gcd(int a, int b, LL &x, LL &y){31 if (!b){32 x = 1, y = 0;33 return a;34 }35 LL res = extend_gcd(b, a % b, y, x);36 y -= a / b * x;37 return res;38 }39 40 inline LL GCD(int a, int p){41 LL x, y, d = extend_gcd(a, p, x, y);42 while (x < 0) x += p;43 return x;44 }45 46 inline LL C(int i, int n, int k, int p){47 return mod[i][n] * GCD(mod[i][n - k] * mod[i][k] % p, p) % p;48 }49 50 inline LL Lucas(int i, int n, int k, int p){51 LL res = 1;52 while (n && k){53 res *= C(i, n % p, k % p, p), res %= p;54 if (!res) return 0;55 n /= p, k /= p;56 }57 return res;58 }59 60 inline LL Chinese(){61 LL M = 1, res = 0;62 for (int i = 0; i < 4; ++i) M *= x[i];63 for (int i = 0; i < 4; ++i){64 LL w = M / x[i], x1, y1, d = extend_gcd(w, x[i], x1, y1);65 res += x1 * w * b[i], res %= M;66 }67 return (res + M) % M;68 }69 70 int main(){71 scanf("%lld%lld", &n, &g);72 g %= p;73 if (!g){74 printf("0\n");75 return 0;76 }77 for (int i = 0; i < 4; ++i){78 mod[i][0] = 1;79 for (int j = 1; j <= x[i]; ++j)80 mod[i][j] = (mod[i][j - 1] * j) % x[i];81 }82 int maxi = (int) sqrt(n);83 for (int i = 1; i <= maxi; ++i)84 if (!(n % i)){85 a[++cnt] = i;86 if (i * i != n) a[++cnt] = n / i;87 }88 89 for (int i = 1; i <= cnt; ++i)90 for (int j = 0; j < 4; ++j){91 b[j] += Lucas(j, n, a[i], x[j]);92 if (b[j] > x[j]) b[j] -= x[j];93 }94 int z = Chinese();95 printf("%lld\n", pow(g, z, p));96 return 0;97 }
BZOJ1951 [Sdoi2010]古代猪文
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。