喵哈哈村的魔法考试 Round #19 (Div.2) B 快速加

题目链接：

题意：

给你a,b,p，让你输出a*b%p的值。0<=a,b,p<=1e18

思路：

两个long long 相乘然后mod p,相乘以后可能会溢出,古有快速幂,现有快速乘法。

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 ll ksj(ll a,ll b,ll p){
19     ll re = 0;
20     while(b){
21         if(b&1) re = (re+a)%p;
22         a = (a+a)%p;
23         b >>= 1;
24     }
25     return re;
26 }
27 
28 // ll ksj(ll a,ll b,ll p){
29 //     if(b==0) return 0;
30 //     if(b==1) return a;
31 
32 //     ll re = ksj(a,b/2,p);
33 //     re = (re+re)%p;
34 //     if(b&1)
35 //         return (re+a)%p;
36 //     else
37 //         return re%p;
38 // }
39 
40 int main(){
41     ll a,b,p;
42     while(cin>>a>>b>>p){
43         cout << ksj(a,b,p) << endl;
44     }
45 
46     return 0;
47 }