远古猪文

【问题讲述】

“在这山底那么边海的那么边发一致众多略肥猪。他们活跃又聪慧,他们调皮又利落。他们自由自在生活于那藏黑色的百般草坪,他们好勇敢互相都关切……”
——选自猪王国民歌
很遥远很久从前,在山之这边海之那边的某片风水宝地曾经有过一个猪王国。猪王国地理地方偏僻,实施之凡适应当下社会的自给自足的庄园经济,很少及外场联系,商贸活动就再也少了。由此呢殊少生另动物知道这样一个帝国。
猪王国尽管未相当,不过土地肥沃,屋舍俨然。假若一定假使将什么与之比来说,这尽管不得不是北宋陶渊明笔下之我们想像着之桃花源了。猪王勤政爱民,猪民安居乐业,邻里团结相处,国家秩序井然,经济蓬勃,社会协调安定。和谐的社会带来为猪民们对工作火红的热忱和针对性将来的桃色之憧憬。
小猪iPig是猪王国的一个百般普通的百姓。小猪2019年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。


题解:

题意就是伸手:

商贸城 1

直接上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 }

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图