1951: [Sdoi2010]远古猪文

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

Description

“在那山的那边海的那边有一批小肥猪。他们活跃又聪慧,他们调皮又利落。他们无拘无缚生活在那米白的大草坪,他们善良勇敢相互都关怀……”
——选自猪王国中国风很久很久从前,在山的那边海的那里的某片八字宝地曾经存在过1个猪王国。猪王国地理地点偏僻,实施的是适应当下社会的自给自足的公园经济,很少与外界联系,商业贸易活动就越来越少了。因而也很少有别的动物知道这么1个帝国。
猪王国即便十分小,可是土地肥沃,屋舍简直。倘诺一定要拿什么与之比较来说,那就只可以是南齐陶渊明笔下的望族想像中的桃花源了。猪王勤政爱民,猪民安居乐业,邻里团结相处,国家秩序井然,经济繁荣,社会协调平安。和谐的社会带给猪民们对工作火红的热心肠和对前景的鲜绿的向往。
小猪iPig是猪王国的三个很平日的人民。小猪今年七周岁了,在大肥猪学校上小学三年级。和超越3/6猪1样,他不是很聪明,由此平常遭逢重重照旧稀奇奇怪或许别人看来毫不费力的作业令她大伤脑筋。小猪后来在场了全猪消息学奥林匹克比赛(Pig
Olympiad in Informatics,
POI),取得了不利的排行,最后保送进入了猪王国民代表大会学(Pig Kingdom University,
PKU)深造。
今后的小猪已经能用计算机消除简单的标题了,比如能用P++语言编写程序计算出A
+
B的值。这一个“成就”已经变为了她津津乐道的话题。当然,不明真相的同窗们也伊始对她尊重啦~
小猪的传说就将随后展开,伴随我们两日时间,希望大家能够欣赏小猪。
标题描述 猪王国的文明礼貌源源不绝,源源不断。
iPig在大肥猪高校教室中查看资料,得知远古一代猪文文字总个数为N。当然,壹种语言要是字数很多,字典也相应会非常的大。当时的猪王国国王思虑到如若修一本字典,规模有相当的大概率远远超越康熙大帝字典,开支的猪力、物力将难以测度。故思量再三没有进展这一项劳猪伤财之举。当然,猪王国的文字后来趁着历史变迁渐渐打开了简化,去掉了有的不常用的字。
iPig打算研讨唐宋有些朝代的猪文文字。依据有关文献记载,那二个朝代流传的猪文文字恰好为远古暂且的k分之一,个中k是N的3个正约数(能够是一和N)。可是现实是哪k分之1,以及k是多少,由于历史过于久远,已经不可能考证了。
iPig觉得假诺顺应文献,每一样能整除N的k都以有望的。他打算思量到持有望的k。分明当k等于有些定值时,该朝的猪文文字个数为N
/ k。可是从N个文字中保留下N /
k个的景况也是一定多的。iPig推断,要是持有十分大恐怕的k的全部景况数加起来为P的话,那么他研讨唐宋文字的代价将会是G的P次方。
未来她想清楚猪王国研商南梁文字的代价是不怎么。由于iPig觉得那个数字只怕是天文数字,所以您只必要报告她答案除以99991165九的余数就能够了。

Input

有且仅有1行:多少个数N、G,用贰个空格分开。

Output

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

Sample Input

4 2

Sample Output

2048

HINT

百分之10的数量中,一 <= N <= 50;
十分之二的多少中,壹 <= N <= 1000;
百分之四十的数量中,一 <= N <= 一千00;
百分百的多少中,1 <= G <= 一千000000,一 <= N <= 一千000000。

Source

Sdoi2010
Contest2

商贸公司 1

题材正是如上//表示平素没读出这么些意思。样例已经表明了,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

对此那种每一种素因子的次数都以一的数来说,大家得以对它分别求解,然后用中华剩余定理去联合

由此大家就利用lucas定理(lucas(n,i,p)=C(n%p,i%p)*lucas(n/p,i/p,p))去求解C对于每1个素数的解

最后再统一就好了

#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;
}

 

发表评论

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

网站地图xml地图