TZOJ 5291 游戏之合成(快速幂快速乘)

描述

zzx和city在玩一款小游戏的时候，游戏中有一个宝石合成的功能，需要m个宝石才可以合成下一级的宝石（例如需要m个1级宝石才能合成2级宝石）。

这时候zzx问city说“我要合成A级宝石需要多少个B级的宝石（A>B）。”

city说：“这数字会好大的。”

zzx：“没事的，你选择一个数取余数就行了，你只要告诉我余数就好了”

city：“那就对梅森素数取余好了”

但最后，由于数字过于大，city又不想手算了，于是想请你帮忙。

输入

多组数据，输入到文件结束为止

每组输入4个正数m,A,B,K，m，A，B为题目描述的意思，K为对第K个梅森素数取余

数据保证M,A,B不会大于第K个梅森素数（K<10）

输出

一个整数为合成A级宝石需要多少个B级的宝石对第K个梅森素数取余的结果

样例输入

5 5 1 2
4 4 1 2

样例输出

2
1

提示

1.第一组样例解释：合成5级宝石需要5个4级的宝石，合成5个4级宝石需要25个3级宝石，以此类推，合成5级宝石需要625颗1级宝石，第2个梅森素数为7，625除7余2.

2.输入输出数据过于庞大，c++输入输出你应该使用scanf和printf，而不是cin和cout

3.梅森素数是由梅森数而来。所谓梅森数，是指形如2^p－1的一类数，其中指数p是素数，常记为Mp 。如果梅森数是素数，就称为梅森素数。

梅森素数表

序号	p	Mp=（2p）-1	Mn的位数	发现时间	发现者
1	2	3	1	古代	古人
2	3	7	1	古代	古人
3	5	31	2	古代	古人
4	7	127	3	古代	古人
5	13	8191	4	1456年	无名氏
6	17	131071	6	1588年	Cataldi
7	19	524287	6	1588年	Cataldi
8	31	2147483647	10	1772年	欧拉
9	61	2305843009213693951	19	1883年	Pervushin
10	89	618970019642690137449562111	27	1911年	Powers

题意

输出合成A级宝石需要多少个B级的宝石对第K个梅森素数取余后的值

题解

典型的快速乘+快速幂m^(A-B）%f[k]，f[k]代表第k个梅森素数

这题当时是比赛的时候做的题，不会存第9个梅森素数所以没做出来

这个题有3个坑：

1.存第9个梅森素数（2305843009213693951LL）

2.m^（A-B）其中A-B太大会超时（快速幂）

3.第9个素数相乘超过19位爆int64（快速乘）

代码

#include<stdio.h>
__int64 multi(__int64 m,__int64 n,__int64 mod){
    __int64 ans=0;
    while(n){
        if(n&1)ans+=m;
        m=(m+m)%mod;
        m%=mod;
        ans%=mod;
        n>>=1;
    }
    return ans;
}
__int64 pow(__int64 a,__int64 n,__int64 mod){
    __int64 ans=1;
    while(n){
        if(n&1)ans=multi(ans,a,mod);
        a=multi(a,a,mod);
        ans%=mod;
        a%=mod;
        n>>=1;
    }
    return ans;
}
int main(){
    __int64 f[]={0,3,7,31,127,8191,131071,524287,2147483647,2305843009213693951LL};//存19位最后加LL
    __int64 m,a,b,k;
    while(scanf("%I64d%I64d%I64d%I64d",&m,&a,&b,&k)!=EOF){
        m%=f[k];
        printf("%I64d
",pow(m,a-b,f[k]));
    }
    return 0;
}