mg4355手机版1951: [Sdoi2010]古代猪文。[SDOI2010]古代猪文。

1951: [Sdoi2010]先猪文

Time Limit: 1 Sec  Memory
Limit: 64 MB
Submit: 2171  Solved: 904
[Submit][Status][Discuss]

问题背景

“在那山底那边海之那边有相同众多略肥猪。他们生龙活虎又聪慧,他们调皮又活。他们自由自在生活于那绿色的不得了草坪,他们好勇敢相互都关切……”

——选自猪王国民谣

老老很久以前,在山之那边海的那里的某片风水宝地曾经是了一个猪王国。猪王国地理位置偏僻,实施的凡适应当下社会之自给自足的园经济,很少和外联系,商贸活动便再次少了。因此为够呛少来另动物知道这么一个帝国。

猪王国虽然不很,但是土地肥沃,屋舍俨然。如果一定要将什么和的相比来说,那就算不得不是东晋陶渊明笔下的门阀想像着之桃花源了。猪王勤政爱民,猪民安
居乐业,邻里和谐相处,国家秩序井然,经济发达,社会协调平稳。和谐之社会带来吃猪民们本着工作火红的热心与对前途之粉色的向往。

多少猪iPig是猪王国的一个分外日常的人民。小猪今年10年份了,在好肥猪学校达标小学三年级。和多数猪一样,他无是非常明白,因此经常遇上很多要么稀奇
古怪或他人看来好的事体让外大伤脑筋。小猪后来到庭了净猪信息学奥林匹克竞赛(Pig
Olympiad in Informatics,
POI),取得了不易的名次,最终保送进入了猪王国大学(Pig Kingdom University,
PKU)深造。

今天之有些猪已经会因此微机解决简单的题材了,比如会为此P++语言编写程序计算出A
+
B的价。这个“成就”已经成了外津津乐道的话题。当然,不明真相的校友等为起对客重啦~

有点猪的故事就以下展开,伴随大家简单天时间,希望大家能够喜欢有些猪。

Description

“在那山的那边海之那边有同居多略肥猪。他们生龙活虎又聪慧,他们调皮又活。他们自由自在生活在那绿色的特别草坪,他们好勇敢相互都关注……”
——选自猪王国风
很遥远很久以前,在山的那么边海的那边的某片风水宝地曾经在过一个猪王国。猪王国地理位置偏僻,实施之是服这社会之自给自足的庄园经济,很少以及外场沟通,商贸活动就还不见了。因此为坏少生任何动物知道这么一个王国。
猪王国虽然不怪,但是土地肥沃,屋舍俨然。如果一定要是拿什么和之比来说,那就算只能是东晋陶渊明笔下的大家想像着之桃花源了。猪王勤政爱民,猪民安居乐业,邻里和睦相处,国家秩序井然,经济蓬勃,社会和谐安定。和谐的社会带来吃猪民们针对工作火红的热忱和针对性前景之粉色的憧憬。
小猪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的余数就可以了。

问题叙述

猪王国的雍容源远流长,博大精深。

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底余数就足以了。

Input

出且仅发生一行:两独数N、G,用一个空格分开。

输入输出格式

输入格式:

输入文件ancient.in有还只发生一行:两个数N、G,用一个空格分开。

输出格式:

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

Output

产生且仅发生一行:一个反复,表示答案除以999911659的余数。

输入输出样例

输入样例#1:

4 2

输出样例#1:

2048

Sample Input

4 2

说明

多少规模

10%的数目被,1 <= N <= 50;

20%底数额遭到,1 <= N <= 1000;

40%之多寡中,1 <= N <= 100000;

100%的数量被,1 <= G <= 1000000000,1 <= N <= 1000000000。

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

 

mg4355手机版 1

但是mg4355手机版 2的x会很老,以至于无法用存储

这要用到指数取模算法

对于G^x,我们有

mg4355手机版 3

 

mg4355手机版 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

 

mg4355手机版 5

 

这时来一个问题:p-1不是素数,不能够因此lucas和求逆元

之所以用p-1分解为4独素数,分别算有和余方程,再用中华剩余定理合并

此描绘来p-1的4独素数:

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 }

 

Sample Output

2048

HINT

10%之数码遭到,1 <= N <= 50;
20%的多少被,1 <= N <= 1000;
40%底数据遭到,1 <= N <= 100000;
100%之数遭到,1 <= G <= 1000000000,1 <= N <= 1000000000。

Source

Sdoi2010
Contest2

mg4355手机版 6

题目就是是如上//表示从没有读出这个意思。样例已经说明了,so~

依据欧拉定理我们得以取

原式为(G^(Σi|n C(n,i) mod 999911658)) mod 999911659

(a^b=a^φ(b) mod b 此处b为素数,so φ(b)=b-1;)

也就是说求解出上试在加以一个飞快幂即使吓了

哪些求解上式呢?

999911658=2*3*4679*35617 是一个Square Free Number

对于这种每个素因子的次数都是1底多次来说,我们好本着其分别求解,然后据此中国剩余定理去联合

所以我们就是用lucas定理(lucas(n,i,p)=C(n%p,i%p)*lucas(n/p,i/p,p))去求解C对于每一个素数的排除

末段再统一就哼了

#include<cstdio>
using namespace std;
typedef long long ll;
const int P=999911659;
int M[5],t[5]={2,3,4679,35617};
int N,G,fac[5][(int)4e4];
int fpow(ll a,ll p,ll mod){
    ll res=1;
    for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;
    return res;
}
int C(int n,int m,int x){
    if(m>n) return 0;
    return fac[x][n]*fpow(fac[x][n-m]*fac[x][m],t[x]-2,t[x])%t[x];
}
void exgcd(int a,int b,ll &x,ll &y){
    if(!b){x=1;y=0;return ;}
    exgcd(b,a%b,x,y);
    ll t=x;x=y;y=t-a/b*y;
}
int lucas(int a,int b,int x){
    if(!b) return 1;
    return C(a%t[x],b%t[x],x)*lucas(a/t[x],b/t[x],x)%t[x];
} 
ll CRT(){
    ll x0,y0,ans=0,Z=P-1;
    for(int i=0;i<4;i++){
        int d=Z/t[i];
        exgcd(d,t[i],x0,y0);
        ans=(ans+d*x0*M[i])%Z;
    }
    while(ans<=0) ans+=Z;
    return ans;
}
int main(){
    scanf("%d%d",&N,&G);
    if(N==G){puts("0");return 0;}
    G%=P;
    for(int i=0;i<4;i++){
        fac[i][0]=1;
        for(int j=1;j<=t[i];j++){
            fac[i][j]=(fac[i][j-1]*j)%t[i];
        }
    }
    for(int i=1,tmp;i*i<=N;i++){
        if(N%i==0){
            tmp=N/i;
            for(int j=0;j<4;j++){
                if(tmp!=i) M[j]=(M[j]+lucas(N,i,j))%t[j];
                M[j]=(M[j]+lucas(N,tmp,j))%t[j];
            }
        }
    }
    printf("%d",fpow(G,CRT(),P));
    return 0;
}

 

相关文章

发表评论

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

*
*
Website