发布时间: 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
输出
输出答案
样例输入1 复制
10 1 7
样例输出1
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 else
14 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 }