1.欧拉公式计算

x^mod p

这里讲当x与p互质时的情况。
所以x%p与p互质,那么就相当于x与p互质,就相当于p是个质数,所以根据欧拉定理

结论

x^mod p=x^(modφ(p)) mod p(当x和p互素)
注:对于素数p, φ(p)=p-1,对于对两个素数p,q φ(pq)=pq-1

2. 同余公式

设c是a除以m的余,即c=a-k*m,也可用同余表达式a≡c (mod m)表示,则可以证明:

    1.1 同余性质1:

对任意整数b

    ab≡bc (mod m) 

证明:

c=a mod m <=> a = km +c

=>ab = k*b*m+bc => ab mod m = (k*b*m + bc)mod m = bc mod m

(1)式等价于:ab mod m =b* (a mod m) mod m,这非常适合递归计算。

    1.2 同余性质2

    a≡c (mod m) => a2≡c2 (mod m)————–(2)

证明:

a=k*m+c =>a2=(km)2+2ckm+c2 =>a2 mod m =c2 mod m,即(2)成立

时间复杂度为O(n),运行时间比较长。

3.反复平方法

进一步研究指数b的二进制表示发现,对任意的整数b都可表示为:

  • n表示b的实际二进制位数
  • bi表示该位是0或1

因此,ab可表示为:

即用b的每一位表示a的每一项,而对任意相邻的两项存在平方关系,即:

因此我们构造下面的算法:

  • 把b转换为二进制表示,并从右至左扫描其每一位(从低到高)
  • 当扫描到第i位时,根据同余性质(2)计算a的第i项的模:

    base变量表示第i-1位时计算出的模,通过递归能很容易地确定所有位的模。
  • 如果第i位为1,即bi=1,则表示该位需要参与模运算,计算结果 result = (result*base) mod m;其中result为前i-1次的计算结果;若bi=0,则表示a的第i项为1,不必参与模运算
#include<bits/stdc++.h>
using namespace std;
int mod_recursion(int m,int n,int k){
    int ans=1;
    for(int i = 0;i < n;i++)
    {
        ans=(ans*m)%k;
    }
    return ans;
}
int mod_rp(int m,int n,int k){
    int ans=1;
    while(n){
        if(n&1)
            ans=ans*m%k;
        n>>=1;
        m=m*m%k;
    }
    return ans;
}

int mod_ora(int m,int n,int k){
    return mod_recursion(m,n%(k-1),k);
    //return mod_rp(m,k-1,k); 
}
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int m,n,k;
    scanf("%d%d%d",&m,&n,&k);
    if(gcd(m,k)){
        cout<<mod_ora(m,n,k)<<endl;
    }
    cout<<mod_recursion(m,n,k)<<endl;
    cout<<mod_rp(m,n,k)<<endl;

    system("pause");
    return 0;
}

发表评论

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