O(1)实现的原理

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

//原理:a*b%p=a*b-a*b/p*p
//用long double转LL进行下取整操作,long double因为是浮点数(12字节),表示范围足以涵盖a*b
int main(){
    LL a,b,p;
    cin>>a>>b>>p;
    a%=p;b%=p;//防止当a,b很大,p很小时,c的值转换成LL后出现溢出(但题目好像没有这样的数据= =)
    //比如这样一组数据 111111111111111111(18个1,可以整除7) 222222222222222222(18个2) 7
    LL c=(long double) a*b/p;
    //虽然a*b与c*p都可能爆LL,但因为a*b-c*p=a*b%p<p,所以二者溢出的高位一定是相同的
    //因此即便爆LL,高位溢出后也不会影响差值
    LL res =((a*b-c*p)%p+p)%p;//保证res一定是0-p-1间的一个整数
    cout<<res<<endl;
}