时间复杂度O(1)

计算a * b mod p
公式a * b = a * b - [a * b / p] * p
记 c = [a * b / p]
x = a * b, y = c * p;
ans = a - y

#include<iostream>
using namespace std;
typedef unsigned long long ull;
ull mul(ull a, ull b, ull p)
{
    ull c = (long double)a * b / p;
    ull x = a * b, y = c * p;
    long long ans = (long long)(x % p) - (long long)(y % p);
    if(ans < 0)ans += p;
    return ans;
}
int main()
{
    long long a, b, p;
    cin >> a >> b >> p;
    cout << mul(a, b, p) << endl;
    return 0;
}