引用
评论
AT1357问题
是这样，最近被一道题好好地 # 了一下。
题目：洛谷 AT1357
求n^p%m
其中1<=n、m<=1000000000 1<=p<=100000000000000
该怎办？
来自：
软件综合
4
不会写快速幂吗
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include<iostream>
using namespace std;
long long qpow(long long a,long long b,long long p)
{
long long ans=1;
while(b>0){
if(b&1)
ans=ans*a%p;
a=a*a%p;
b/=2; }
return ans;}
int main(){
long long b,p,k,ans;
cin>>b>>p>>k;
ans=qpow(b,p,k);
cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans;}<br></p>
引用
评论
我的是这样的
#include<iostream>using namespace std;unsigned long long n,m,p;//n^m%punsigned long long f(unsigned long long x){ if(x==1) return n%p; if(x%2==0) //完全二分 { unsigned long long j=f(x/2); //储存f的值，不用调用2次 return j*j%p; } else { unsigned long long j=f((x-1)/2); return j*j*n%p; }}int main(){ cin>>n>>m>>p; cout<<f(m); return 0;}
引用
评论