64位整數乘法
求a乘b對p取模的值，
眾所周知，64位整數乘以64位整數最大是可以達到128位的，所以使用long long就肯定會爆炸，所以我們可以使用128位整數，
#include <bits/stdc++.h>
using namespace std;
int main() {
long long _a, _b, _p;
cin >> _a >> _b >> _p;
__int128 a = _a, b = _b, p = _p;
_p = a * b % p;
cout << _p << endl;
}
那么我們如何能夠不使用這樣比較作弊的方案呢？
有一個類似于快速冪的思想，既然直接乘會爆炸，那我們把b拆成n個2^k的和，一點一點乘，反正最后取模和邊做邊取模是一樣的，
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a, b, p;
cin >> a >> b >> p;
ll res = 0;
while(b){
if(b & 1)res += a, res %= p;
a *= 2, a %= p;
b >>= 1;
}
cout << res << endl;
}
當然我們還可以有更騷的操作
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a, b, p;
cin >> a >> b >> p;
cout << (a * b - (ll)((long double) a / p * b ) * p + p ) % p << endl;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41160.html
標籤：其他
上一篇：【學習筆記】計算理論