Description

“在那山的这边海的那边有一堆小肥猪。他们活跃又聪慧,他们调皮又利落。他们自由自在生活在那郎窑红的大草坪,他们善良勇敢相互都关心……”
——选自猪王国爵士乐很久从古至今,在山的那边海的那里的某片八字宝地曾经存在过3个猪王国。猪王国地理地方偏僻,实施的是适应当下社会的自给自足的庄园经济,很少与外面联系,商业贸易活动就越来越少了。因而也很少有其余动物知道这样一个王国。
猪王国就算相当的小,不过土地肥沃,屋舍简直。假如一定要拿什么与之比较来说,那就不得不是齐国陶渊明笔下的门阀想象中的桃花源了。猪王勤政爱民,猪民安居乐业,邻里和谐相处,国家秩序井然,经济繁荣,社会协调安定。和谐的社会带给猪民们对工作火红的热忱和对前景的普鲁士蓝的憧憬。
小猪iPig是猪王国的2个很壹般的平民。小猪今年七岁了,在大肥猪高校上小学三年级。和大部分猪一样,他不是很领会,因而平时蒙受不少也许稀奇古怪只怕外人看来十拿九稳的事体令他大伤脑筋。小猪后来列席了全猪音讯学奥林匹克比赛(Pig
Olympiad in Informatics,
POI),取得了不错的排名,最后保送进入了猪王国民代表大会学(Pig Kingdom University,
PKU)深造。
未来的小猪已经能用总计机化解不难的标题了,比如能用P++语言编写程序计算出A
+
B的值。那个“成就”已经改为了她津津乐道的话题。当然,不明真相的同室们也伊始对他珍重啦~
小猪的故事就将随后展开,伴随大家两日时间,希望大家能够欣赏小猪。
标题描述 猪王国的文武源源不绝,源远流长。
iPig在大肥猪高校体育场合中查看资料,得知远古近年来猪文文字总个数为N。当然,1种语言假诺字数很多,字典也呼应会十分大。当时的猪王国圣上思考到借使修一本字典,规模有十分大希望远远当先玄烨字典,开支的猪力、物力将难以估计。故思量再三未有展开那1项劳猪伤财之举。当然,猪王国的文字后来乘机历史转变慢慢展开了简化,去掉了部分不常用的字。
iPig打算钻探东晋有个别朝代的猪文文字。依据相关文献记载,那几个朝代流传的猪文文字恰好为远古时期的k分之壹,个中k是N的八个正约数(可以是壹和N)。但是具体是哪k分之1,以及k是多少,由于历史过于久远,已经不能够考证了。
iPig觉得借使顺应文献,每1种能整除N的k都是有十分大概率的。他打算思量到独具可能的k。明显当k等于有个别定值时,该朝的猪文文字个数为N
/ k。可是从N个文字中保留下N /
k个的意况也是一对一多的。iPig推测,假如持有希望的k的全数意况数加起来为P的话,那么她钻探古时候文字的代价将会是G的P次方。
今后她想知道猪王国研讨北魏文字的代价是稍稍。由于iPig觉得那一个数字大概是天文数字,所以您只要求报告她答案除以99991165玖的余数就能够了。

Input

有且仅有壹行:四个数N、G,用3个空格分开。

Output

有且仅有1行:一个数,表示答案除以99991165九的余数。

Sample Input

4 2

Sample Output

2048

HINT

一成的多寡中,一 <= N <= 50;
伍分一的数目中,1 <= N <= 一千;
四成的多少中,一 <= N <= 一千00;
百分百的数目中,1 <= G <= 一千000000,一 <= N <= 一千000000。

 

正解:费马小定理+$lucas$定理+中中原人民共和国剩余定理+扩张欧几里得定理+神速幂。

 

第2弄清题意,题目供给的是$Ans=g^{\sum_{d|n}C_{n}^{d}}$

因为模数是质数,所以由费马小定理得,$g^{\sum_{d|n}C_{n}^{d}}=g^{\sum_{d|n}C_{n}^{d}
\mod (p-1)}$

接下来我们渴求$\sum_{d|n}C_{n}^{d} \mod (p-一)$,不过$p-一$不是质数。

我们把$p-一$拆开,变成$四$个质数,然后对于各类模数用$lucas$定理求出$C_{n}^{d}$,最终再用中夏族民共和国剩余定理合并就行了。

 

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define rhl (999911659)
15 #define inf (1<<30)
16 #define il inline
17 #define RG register
18 #define ll long long
19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
20 
21 using namespace std;
22 
23 const int p[5]={0,2,3,4679,35617};
24 
25 ll fac[1000010],inv[1000010],a[5],n,g,pp,ans;
26 
27 il ll gi(){
28     RG ll x=0,q=1; RG char ch=getchar();
29     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
30     if (ch=='-') q=-1,ch=getchar();
31     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
32     return q*x;
33 }
34 
35 il ll qpow(RG ll a,RG ll b,RG ll p){
36     RG ll ans=1;
37     while (b){
38     if (b&1) ans=ans*a%p;
39     a=a*a%p,b>>=1;
40     }
41     return ans;
42 }
43 
44 il ll cm(RG ll n,RG ll m,RG ll p){
45     if (n<m) return 0;
46     return fac[n]*inv[fac[m]]%p*inv[fac[n-m]]%p;
47 }
48 
49 il ll lucas(RG ll n,RG ll m,RG ll p){
50     if (!m) return 1; RG ll res=cm(n%p,m%p,p);
51     if (!res) return 0; return res*lucas(n/p,m/p,p)%p;
52 }
53 
54 il void exgcd(RG ll a,RG ll b,RG ll &x,RG ll &y){
55     if (!b){ x=1,y=0; return; }
56     exgcd(b,a%b,y,x); y-=a/b*x; return;
57 }
58 
59 il void work(){
60     n=gi(),g=gi()%rhl,pp=rhl-1,inv[1]=fac[0]=fac[1]=1;
61     if (g==0){ puts("0"); return; }
62     for (RG ll i=1;i<=4;++i){
63     for (RG ll j=2;j<=p[i];++j){
64         fac[j]=fac[j-1]*j%p[i];
65         inv[j]=(p[i]-p[i]/j)*inv[p[i]%j]%p[i];
66     }
67     for (RG ll j=1;j*j<=n;++j){
68         if (n%j) continue;
69         if (j*j==n) (a[i]+=lucas(n,j,p[i]))%=p[i];
70         else{
71         (a[i]+=lucas(n,j,p[i]))%=p[i];
72         (a[i]+=lucas(n,n/j,p[i]))%=p[i];
73         }
74     }
75     RG ll c=pp/p[i],d=p[i],x=0,y=0;
76     exgcd(c,d,x,y); while (x<=0) x+=d;
77     (ans+=x*c%pp*a[i])%=pp;
78     }
79     printf("%lld\n",qpow(g,ans,rhl)); return;
80 }
81 
82 int main(){
83     File("pig");
84     work();
85     return 0;
86 }

 

发表评论

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

网站地图xml地图