首页 > 代码库 > qscoj 128 喵哈哈村的魔法源泉（2）(模仿快速幂，好题)
qscoj 128 喵哈哈村的魔法源泉（2）(模仿快速幂，好题)
喵哈哈村的魔法源泉（2）
发布时间: 2017年5月9日 20:59 最后更新: 2017年5月9日 21:00 时间限制: 1000ms 内存限制: 128M
喵哈哈村有一个魔法源泉，里面有无穷无尽的力量。
但是前提是你能答出这样一个问题：
给你a,b,p，让你输出a*b%p的值。
本题包含若干组测试数据。
第一行三个整数a,b,p。
满足：0<=a,b,p<=1e18
输出答案
复制
10 1 7
3
题目链接：http://qscoj.cn/problem/128/
题解：卿学姐说首先快速幂是来处理次方的问题，那么我们模仿快速幂，写一个快速加即可，这样我们每次乘以2，就不会爆longlong了
这里要注意，没加while会WA，这里卡就卡这个！
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll a,b,p; 5 ll gcd(ll a,ll b)//模仿快速幂解法 6 { 7 if(b==0) 8 return 0; 9 ll res=gcd(a,b/2);10 res=(res+res)%p;11 if(b&1)12 return (res+a)%p;13 else14 return res;15 }16 int main()17 {18 while(scanf("%lld%lld%lld",&a,&b,&p)!=EOF)19 {20 cout<<gcd(a,b)<<endl;21 }22 return 0;23 }
qscoj 128 喵哈哈村的魔法源泉（2）(模仿快速幂，好题)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。