AT1357问题

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

题目:洛谷 AT1357

求n^p%m

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

该怎办?

来自:计算机科学 / 软件综合
2018-6-15 14:35:46
1楼

2018-06-15 14-27-34屏幕截图.png


 

2018-06-15 14-27-43屏幕截图.png

 

 

2018-06-15 14-32-37屏幕截图.png

 

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

折叠评论
加载评论中,请稍候...
折叠评论
2018-6-15 19:56:21
154454496
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;}<br></p>

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

折叠评论
加载评论中,请稍候...
折叠评论
2018-06-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;}

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

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

Johnsons
进士 机友 笔友
文章
34
回复
216
学术分
0
2018/01/06注册,9 天前活动

蒟蒻oier

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
插入表情
我的表情
共享表情
Emoji
上传
注意事项
最大尺寸100px,超过会被压缩。为保证效果,建议上传前自行处理。
建议上传自己DIY的表情,严禁上传侵权内容。
点击重试等待上传{{s.progress}}%处理中...已上传
空空如也~
草稿箱
加载中...
此处只插入正文,如果要使用草稿中的其余内容,请点击继续创作。
{{fromNow(d.toc)}}
{{getDraftInfo(d)}}
标题:{{d.t}}
内容:{{d.c}}
继续创作
删除插入插入
{{forum.displayName}}
{{forum.countThreads}}
篇文章,
{{forum.countPosts}}
条回复
{{forum.description || "暂无简介"}}
ID: {{user.uid}}
学术分隐藏
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png