输出一个整数，表示a*b mod p的值。

数据范围

1≤a,b,p≤1018

1
2
3
4
5
6
7
8
9
10
11
ll qadd(ll a, ll b, ll p)
{
    ll res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

利用longlong取模溢出相抵消

1
2
3
4
5
6
7
8
9

ll  mul(ll x,ll y,ll m){
	x%=m;y%=m;
	ll d=((long double )x*y/m);
	d=x*y-d*m;
	if(d>=m)d-=m;
	if(d<0)d+=m;
	return d;
}