Biết rằng (a ∗ b)modc=((amodc) ∗ (bmodc))modc,

Ví dụ: (10 ∗ 3)mod4=2 và (((10mod4) ∗ (3mod4)))mod4=6mod4=2; trong khi đó giới hạn biểu diễn của long long là cỡ 18 chữ số, hãy tính (a ∗ b)modc khi mà tích (a ∗ b) có thể vượt quá khả năng biểu diễn của long long trong 

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

long long check(long long a, long long b, long long c)
{
    if (b == 0)
        return 0;

    long long x = check(a, b / 2, c) % c;

    if (b & 1)
        return ((x + x) % c + a % c) % c;
    else
        return (x + x) % c;
}

int main(){
    long long a,b,c;
    cin>>a>>b>>c;
    cout<< check(a,b,c)<<endl;
    return 0;
}