AT1357问题

是这样,最近被一道题好好地 # 了一下。

题目:洛谷 AT1357

求n^p%m

其中1<=n、m<=1000000000 1<=p<=100000000000000

该怎办?

来自 软件综合
2018-6-15 14:35:46
1楼


 

 

 

 

[修改于 1 年前 - 2018-06-15 14:37:49]

折叠评论
加载评论中,请稍候...
折叠评论
2楼

不会写快速幂吗

https://www.luogu.org/recordnew/show/6540485

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

[修改于 1 年前 - 2018-06-15 19:58:10]

折叠评论
加载评论中,请稍候...
折叠评论
2018-6-16 15:40:36
Johnsons(作者)
3楼

我的是这样的

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

折叠评论
加载评论中,请稍候...
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

ID:{{user.uid}}
{{user.username}}
{{user.info.certsName}}
{{user.description}}
{{format("YYYY/MM/DD", user.toc)}}注册,{{fromNow(user.tlv)}}活动
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png