关键词：
古代猪文
【问题描述】
“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……” ——选自猪王国民歌 很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。 猪王国虽然不大，但是土地肥沃，屋舍俨然。如果一定要拿什么与之相比的话，那就只能是东晋陶渊明笔下的大家想象中的桃花源了。猪王勤政爱民，猪民安居乐业，邻里和睦相处，国家秩序井然，经济欣欣向荣，社会和谐稳定。和谐的社会带给猪民们对工作火红的热情和对未来的粉色的憧憬。 小猪iPig是猪王国的一个很普通的公民。小猪今年10岁了，在大肥猪学校上小学三年级。和大多数猪一样，他不是很聪明，因此经常遇到很多或者稀奇古怪或者旁人看来轻而易举的事情令他大伤脑筋。小猪后来参加了全猪信息学奥林匹克竞赛(Pig Olympiad in Informatics, POI)，取得了不错的名次，最终保送进入了猪王国大学(Pig Kingdom University, PKU)深造。 现在的小猪已经能用计算机解决简单的问题了，比如能用P++语言编写程序计算出A + B的值。这个“成就”已经成为了他津津乐道的话题。当然，不明真相的同学们也开始对他刮目相看啦~ 小猪的故事就将从此展开，伴随大家两天时间，希望大家能够喜欢小猪。 题目描述 猪王国的文明源远流长，博大精深。 iPig在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为N。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。 iPig打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的k分之一，其中k是N的一个正约数（可以是1和N）。不过具体是哪k分之一，以及k是多少，由于历史过于久远，已经无从考证了。 iPig觉得只要符合文献，每一种能整除N的k都是有可能的。他打算考虑到所有可能的k。显然当k等于某个定值时，该朝的猪文文字个数为N / k。然而从N个文字中保留下N / k个的情况也是相当多的。iPig预计，如果所有可能的k的所有情况数加起来为P的话，那么他研究古代文字的代价将会是G的P次方。 现在他想知道猪王国研究古代文字的代价是多少。由于iPig觉得这个数字可能是天文数字，所以你只需要告诉他答案除以999911659的余数就可以了。
【输入格式】
有且仅有一行：两个数N、G，用一个空格分开。
【输出格式】
有且仅有一行：一个数，表示答案除以999911659的余数。
【样例输入】
4 2
【样例输出】
2048
【数据范围】
10%的数据中，1 <= N <= 50；
20%的数据中，1 <= N <= 1000；
40%的数据中，1 <= N <= 100000；
100%的数据中，1 <= G <= 1000000000，1 <= N <= 1000000000。
题解:
题意就是求：
直接上Crt，由于999911658刚好分解出四个质数，所以对于Crt中的每个答案可以直接使用Lucas定理和阶乘组合数求出
1 #include<cmath> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 typedef long long lo; 9 const int mod = 999911658; 10 const int maxs = 4e4; 11 const int maxp = 4e4; 12 const int p[] = {2, 3, 4679, 35617}; 13 int n, g; 14 int num; 15 int c[maxs], a[maxs]; 16 int fac[4][maxp], inv[4][maxp]; 17 inline void Scan(int &x) 18 { 19 char c; 20 bool o = false; 21 while(!isdigit(c = getchar())) o = (c != '-') ? o : true; 22 x = c - '0'; 23 while(isdigit(c = getchar())) x = x * 10 + c - '0'; 24 if(o) x = -x; 25 } 26 inline int Pow(int x, int n, int mo) 27 { 28 int sum = 1; 29 while(n) 30 { 31 if(n & 1) sum = (lo) sum * x % mo; 32 x = (lo) x * x % mo; 33 n >>= 1; 34 } 35 return sum; 36 } 37 inline void Sep() 38 { 39 int s = sqrt(n); 40 for(int i = 1; i <= s; ++i) 41 if(!(n % i)) 42 c[++num] = i, c[++num] = n / i; 43 if(s * s == n) --num; 44 } 45 inline void Mod(int &x, int mod) 46 { 47 if(x >= mod) x -= mod; 48 } 49 inline int Lucas(int i, int n, int m, int k) 50 { 51 if(!m) return 1; 52 if(n == m) return 1; 53 if(n < k) return (lo) fac[i][n] * inv[i][m] % k * inv[i][n - m] % k; 54 return (lo) Lucas(i, n % k, m % k, k) % k * Lucas(i, n / k, m / k, k) % k; 55 } 56 inline void Exgcd(int a, int b, int &x, int &y) 57 { 58 if(!b) x = 1, y = 0; 59 else 60 { 61 Exgcd(b, a % b, y, x); 62 y -= x * (a / b); 63 } 64 } 65 inline int Inv(int a, int b) 66 { 67 int g, x, y; 68 Exgcd(a, b, x, y); 69 if(x < 0) x += b; 70 return x; 71 } 72 inline int Ask() 73 { 74 int sum = 0; 75 int g, h; 76 for(int i = 0; i <= 3; ++i) 77 { 78 g = mod / p[i]; 79 h = Inv(g, p[i]); 80 sum += (lo) g * h % mod * a[i] % mod; 81 Mod(sum, mod); 82 } 83 return sum; 84 } 85 int main() 86 { 87 Scan(n), Scan(g); 88 Sep(); 89 for(int l = 0; l <= 3; ++l) 90 { 91 int k = p[l]; 92 fac[l][0] = 1, inv[l][0] = 1; 93 for(int i = 1; i < k; ++i) fac[l][i] = (lo) fac[l][i - 1] * i % k; 94 inv[l][k - 1] = Pow(fac[l][k - 1], k - 2, k); 95 for(int i = k - 2; i >= 1; --i) inv[l][i] = (lo) inv[l][i + 1] * (i + 1) % k; 96 } 97 for(int i = 1; i <= num; ++i) 98 for(int j = 0; j <= 3; ++j) 99 a[j] += Lucas(j, n, c[i], p[j]), Mod(a[j], p[j]); 100 int ans = Ask(); 101 if(g != mod + 1) printf("%d", Pow(g, ans, mod + 1)); 102 else printf("0"); 103 }
bzoj1951[sdoi2010]古代猪文
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。 本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！ 题目链接... 查看详情
古代猪文bzoj1951
古代猪文【问题描述】“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海的那边... 查看详情
bzoj1951sdoi2010—古代猪文
http://www.lydsy.com/JudgeOnline/problem.php?id=1951 (题目链接)题意 废话一堆。。求解：Solution 真的是数论经典题，什么都用上了。 因为费马小定理，每p-1个g相乘会得到1，那么容易得到： 所以现在关键是求： ... 查看详情
bzoj1951[sdoi2010]古代猪文lucas定理+crt
【BZOJ1951】[Sdoi2010]古代猪文Description求$X=sumlimits_{d|n}C_n^d$，$Ans=G^X(mod999911659)$。Input有且仅有一行：两个数N、G，用一个空格分开。Output有且仅有一行：一个数，表示答案除以999911659的余数。SampleInput42SampleOutput2048HINT10%的数据中，1... 查看详情
bzoj1951:[sdoi2010]古代猪文
传送门数论的套路似乎没多少..很容易得到答案$ans=G^{C(N,i)}$其中$i$为$N$的因数。很显然，我们可以在$O(logN)$的时间内算出所有的因数，但是怎么算大组合数呢？大力Lucas。然而指数应该模$P-1$，$P-1$不是质数啊，这就很痛苦啊。通... 查看详情
bzoj1951[sdoi2010]古代猪文(代码片段)
[Sdoi2010]古代猪文TimeLimit:1SecMemoryLimit:64MBDescription“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以... 查看详情
bzoj1951[sdoi2010]古代猪文
【算法】欧拉定理+组合数取模(lucas)+中国剩余定理(CRT)【题解】给定G,N先考虑简化幂运算，因为模数为素数，由欧拉定理可知G^k=G^(k%φ(p))modp，显然G^(k%φ(p))modp可以用快速幂求解此时观察到2p>max(n)>p，所以可能n=p，此时不满足n... 查看详情
bzoj1951:[sdoi2010]古代猪文
数论综合。费马小定理，lucas定理，中国剩余定理，exgcd，快速幂，乘法逆元。首先要计算出n的每个约数，简单的sqrt(n)枚举即可。然后计算C(i,m)(m个中挑i个的组合数，ps:因为网上正反俩种都有，所以标注一下。。)设s=sum(C(i,m))题... 查看详情
[bzoj1951][sdoi2010]古代猪文（lucas+crt+费马小定理）
Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海... 查看详情
bzoj1951:[sdoi2010]古代猪文中国剩余定理+欧拉定理+组合数学+卢卡斯定理
首先化简，题目要求的是[G^{sum_{i|n}C_{n}^{i}}\%p]对于乘方形式快速幂就行了，因为p是质数，所以可以用欧拉定理[G^{sum_{i|n}C_{n}^{i}\%varphi(p)}][G^{sum_{i|n}C_{n}^{i}\%p-1}]因为p-1不是质数，所以把它质因数分解为2,3,4679,35617，最后用中国剩... 查看详情
1951:[sdoi2010]古代猪文
1951:[Sdoi2010]古代猪文TimeLimit: 1Sec MemoryLimit: 64MBSubmit: 2171 Solved: 904[Submit][Status][Discuss]Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在 查看详情
1951:[sdoi2010]古代猪文
Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝... 查看详情
[bzoj1951][sdoi2010]古代猪文费马小定理+lucas定理+crt(代码片段)
Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝... 查看详情
p2480[sdoi2010]古代猪文(代码片段)
P2480[SDOI2010]古代猪文题目背景“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久... 查看详情
[sdoi2010]古代猪文(代码片段)
题解：一看就是一道数学题了。根据欧拉定理，必须要处理的是$sum_i|nC(n,i)spacemodspacephi(p)$令A等于这个大式子。phi(p)=999911658=2*3*4679*35617是四个质数的乘积。看来就类似扩展LUCAS了。但是，指数只有1所以，我们可以求出：A=a1mod2A=a2... 查看详情
「sdoi2010」古代猪文lucas+中国剩余定理(代码片段)
题意：猪王国的文明源远流长，博大精深。iPig在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为N。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远... 查看详情
学术篇sdoi2010古代猪文
这里可能包含传送门又双叒叕数论大杂烩...定理什么我都不会证题目很长很啰嗦但是题意很显然...化完式子之后就是这么个东东:(G^{sum_{k|n}C_k^{frac{n}{k}}}modp)看上去好像也并不怎么好求...而(p)是个质数,由于费马小定理,我们知道(G^{... 查看详情
洛谷p2480[sdoi2010]古代猪文
要求（图是盗来的QAQ）首先用欧拉定理把幂模一下，直接就是MOD-1了然后发现MOD-1可以分解为2,3,4679,35617，都是质数，可以直接用Lucas定理然后用中国剩余定理合并一下即可千万不可把MOD和MOD-1搞混了，否则调试好麻烦的1#include<c... 查看详情