莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路1：

分解b，让b个a相加

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

//龟速乘，计算res = a * b % p
LL qmul(LL a,LL b,LL p)
{
    LL res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=a*2%p;
        b>>=1;
    }
    return res;
}

int main()
{
    LL a,b,p;

    cin>>a>>b>>p;

    cout<<qmul(a,b,p)<<endl;

    return 0;
}

思路2：

利用__128int完成64位整数乘法, 3e38 < 2 ^ 128 < 4e38

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,b,p;

int main ()
{
    cin>>a>>b>>p;

    __int128 ap=a,bp=b,pp=p;

    ll ans=(ap*bp)%pp;

    cout<<ans<<endl;

    return 0;
}