古猪文

【问题讲述】

“在那山之那么边海的那么边发平等博略肥猪。他们活跃又聪慧,他们调皮又利落。他们自由自在生活于那绿色的万分草坪,他们好勇敢相互都关心……”
——选自猪王国民歌
很长远很久以前,在山之那边海之那里的某片风水宝地曾经有过一个猪王国。猪王国地理位置偏僻,实施的凡适应当下社会的自给自足的花园经济,很少及外界联系,商贸活动便重少了。因此也死少发生其他动物知道这么一个帝国。
猪王国虽然非坏,但是土地肥沃,屋舍俨然。如果一定要将什么和的相比来说,那便只能是东晋陶渊明笔下之大家想像着的桃花源了。猪王勤政爱民,猪民安居乐业,邻里和谐相处,国家秩序井然,经济繁荣,社会协调安定。和谐的社会带来被猪民们针对工作火红的热忱和针对性前景底桃色之憧憬。
小猪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。


题解:

题意就是要:

商贸公司 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地图