快速幂取模，快速乘取模 - 平头弟

快速幂取模，快速乘取模

2019-04-13 14:32发布生成海报

站内文章 / 模拟电子

9708 0

首先得知道余数有如下性质：

(a+b)％m == (a％m+b％m)％m
a*b%c=((a%c)*b)%c
ab%c=(a%c)*b%c
a^p%p=aa…*a%p=(a%p) *(a%p) * … *(a%p)
代码：
快速幂取模

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL  quickMod(LL a, LL p, LL mod) {
	a%=mod;
    LL base=1;
    while(p) {
        if(p&1) base=base*a%mod;
        a=a*a%mod; 
		p>>=1;
    }
    return base;
}
int main(){
	int a,p,mod;
	scanf("%d%d%d",&a,&p,&mod); 
	printf("%d
",quickMod(a,p,mod));
}

快速乘取模

#include<cstdio>
#include<iostream>

using namespace std;

typedef long long ll;
ll ksc(ll a,ll b,ll p){
	ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}
int main(){
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans=ksc(a,b,p);
	cout<<ans<<endl;
}

Ta的文章更多 >>

热门文章