【题目】
求a乘b对p取模的值，其中a，b，p均小于等于1e18大于等于1
【算法】
类似快速幂的二进制思想，将b看作一个二进制数展开为各个二进制位的值相加取模
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll a,b,p,ans,cur; 5 int main() 6 { 7 cin>>a>>b>>p; 8 for(; b; b>>=1) 9 { 10 if(b&1) ans = (ans+a) % p; 11 a = a * 2 % p; 12 } 13 cout << ans << endl; 14 }
---------------------------------------------------------------------------------------------------------------------
【算法】
a * b mod p = a * b - [a*b/p] * p （感觉这种有点不靠谱，最好别用，涉及浮点就开始玄学了）
1 //玄学做法 2 #include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 ll a,b,p,c,ans; 6 int main() 7 { 8 cin>>a>>b>>p; 9 a %= p; 10 b %= p; 11 long long c = (long double)a * b / p; 12 ans = a*b - c*p; 13 if(ans >= p) ans -= p; 14 else if(ans < 0) ans += p; 15 cout << ans << endl; 16 }