题材背景

“在这山的那边海的那边有一群小肥猪。他们龙腾虎跃又聪慧,他们调皮又利落。他们无拘无缚生活在那铁锈棕的大草坪,他们善良勇敢互相都关心……”

商贸公司,——选自猪王国重打击乐

很久很久此前,在山的这边海的那里的某片八字宝地曾经存在过3个猪王国。猪王国地理地点偏僻,实施的是适应当下社会的自给自足的庄园经济,很少与外面联系,商业贸易活动就更少了。因而也很少有别的动物知道这么3个帝国。

猪王国即便十分小,然则土地肥沃,屋舍简直。借使一定要拿什么与之相比来说,那就只好是明清陶渊明笔下的门阀想象中的桃花源了。猪王勤政爱民,猪民安
居乐业,邻里团结相处,国家秩序井然,经济繁荣,社会协调地西泮。和谐的社会带给猪民们对工作火红的热心和对未来的橄榄棕的向往。

小猪iPig是猪王国的贰个很平日的全体公民。小猪二零一九年7虚岁了,在大肥猪学校上小学三年级。和多数猪一样,他不是很聪慧,由此平常境遇重首要么稀奇
古怪恐怕外人看来不费吹灰之力的业务令他大伤脑筋。小猪后来在座了全猪消息学奥林匹克竞技(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的余数就足以了。

输入输出格式

输入格式:

输入文件ancient.in有且仅有一行:五个数N、G,用一个空格分开。

输出格式:

输出文件ancient.out有且仅有一行:一个数,表示答案除以999911659的余数。

输入输出样例

输入样例#1:

4 2

输出样例#1:

2048

说明

数量规模

1/10的数码中,1 <= N <= 50;

五分之一的多寡中,1 <= N <= 一千;

百分之四十的数目中,1 <= N <= 一千00;

百分之百的多少中,1 <= G <= 一千000000,1 <= N <= 1000000000。

题目大意:给定N,G,求

 

商贸公司 1

但是商贸公司 2的x会不小,以至于不可能用存款和储蓄

此刻要用到指数取模算法

对于G^x,我们有

商贸公司 3

 

商贸公司 4

 

上面给出注明

因为Gμ(p)≡1  (mod
p)

我们令x=k*μ(p)+b

那么Gx=(Gμ(p))^k*Gb

因为(Gμ(p))^k≡1  (mod p)**

**因为b=x%μ(p)=x%(p-1)**

所以Gx≡Gx%(p-1)   (mod
p)

之所以对指数取模,模p-1就行了

组成数取模用Lucas

 

商贸公司 5

 

那儿有1个难点:p-1不是素数,无法用lucas和求逆元

从而将p-1分解为5个素数,分别算出同余方程,再用中中原人民共和国剩余定理合并

这里写出p-1的多少个素数:

999911658=2*3*4679*35617

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 ll Mod=999911658;
 8 ll fac[100001],A[100001],cnt,ys[100001],n,g,pri[5],b[5],c[5],a[5];
 9 ll exgcd(ll a,ll b,ll &x,ll &y)
10 {
11   if (b==0)
12     {
13       x=1;y=0;
14       return a;
15     }
16   ll d=exgcd(b,a%b,x,y);
17   ll t=x;x=y;y=t-(a/b)*y;
18   return d; 
19 }
20 ll rev(ll a,ll p)
21 {
22   ll x,y;
23   exgcd(a,p,x,y);
24   return (x%p+p)%p;
25 }
26 ll C(ll x,ll y,ll p)
27 {
28   if (x>y) return 0;
29   if (x<p&&y<p) return (fac[y]*A[x]%p)*A[y-x]%p;
30   return C(x%p,y%p,p)*C(x/p,y/p,p)%p;
31 }
32 ll qpow(ll x,ll y,ll p)
33 {
34   ll res=1;
35   while (y)
36     {
37       if (y&1) res=res*x%p;
38       x=x*x%p;
39       y/=2;
40     }
41   return res;
42 }
43 ll cal(int p)
44 {int i;
45   fac[0]=1;
46   for (i=1;i<p;i++)
47     fac[i]=fac[i-1]*i%p;
48   A[1]=1;A[0]=1;
49   for (i=2;i<p;i++)
50     A[i]=(p-p/i)*A[p%i]%p;
51   for (i=1;i<p;i++)
52     A[i]=A[i]*A[i-1]%p;
53   ll s=0;
54   for (i=1;i<=cnt;i++)
55     {
56       s+=C(ys[i],n,p);
57       s%=p;
58     }
59   return s;
60 }
61 int main()
62 {int i;
63   cin>>n>>g;
64   if (g==Mod+1)
65     {
66       cout<<0;
67       return 0;
68     }
69   for (i=1;i*i<=n;i++)
70       if (n%i==0)
71     {
72       if (i*i==n)
73           ys[++cnt]=i;
74       else 
75         {
76           ys[++cnt]=i;
77           ys[++cnt]=n/i;
78         }
79     }
80   pri[1]=2;pri[2]=3;pri[3]=4679;pri[4]=35617;
81   for (i=1;i<=4;i++)
82     b[i]=cal(pri[i]);
83   for (i=1;i<=4;i++) 
84     c[i]=Mod/pri[i];
85   for (i=1;i<=4;i++)
86     a[i]=rev(c[i],pri[i]);
87   ll s=0;
88   for (i=1;i<=4;i++)
89     {
90       s+=((c[i]*a[i]%Mod)*b[i])%Mod;
91       s%=Mod;
92     }
93   printf("%lld\n",qpow(g,s,Mod+1));
94 }

 

发表评论

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

网站地图xml地图