太古猪文

【难题讲述】

“在那山的那边海的那边有一群小肥猪。他们龙精虎猛又聪慧,他们调皮又利落。他们落拓不羁生活在那土红的大草坪,他们善良勇敢互相都关切……”
——选自猪王国乡村音乐很久很久在此之前,在山的那边海的那里的某片八字宝地曾经存在过二个猪王国。猪王国地理地方偏僻,实施的是适应当时社会的自给自足的园林经济,很少与外边调换,商业贸易活动就更少了。由此也很少有任何动物知道那样二个王国。
猪王国纵然十分小,可是土地肥沃,屋舍简直。要是一定要拿什么与之相比较来说,这就只可以是隋代陶渊明笔下的门阀想象中的桃花源了。猪王勤政爱民,猪民安居乐业,邻里和谐相处,国家秩序井然,经济景气,社会和谐稳定。和谐的社会带给猪民们对工作火红的热情和对今后的高粱红的憧憬。
小猪iPig是猪王国的1个很平凡的全体成员。小猪今年八虚岁了,在大肥猪高校上小学三年级。和当先四分之一猪一样,他不是很聪明伶俐,由此平日碰到许多照旧稀奇古怪只怕别人看来不费吹灰之力的作业令他大伤脑筋。小猪后来出席了全猪音讯学奥林匹克比赛(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,用3个空格分开。

【输出格式】

有且仅有一行:二个数,表示答案除以999911659的余数。

【样例输入】

商贸公司,4 2

【样例输出】

2048

【数据范围】

一成的多寡中,1
<= N <= 50;
伍分之一的数码中,1
<= N <= 一千;
五分之二的多寡中,1
<= N <= 一千00;
百分百的数目中,1
<= G <= 一千000000,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地图