题目描述

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数aa，第二行输入整数bb，第三行输入整数pp。

输出格式

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

数据范围

1≤a,b,p≤10181≤a,b,p≤1018

输入样例：

3
4
5

输出样例：

2

题解：

a * b
a + a + a + a + a + a +...+ a
a * 1 = a
a * 2 = 2a
a * 3 = 3a
...
a * (2^k) = 2^k * a

代码：

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

long long a,b,mod;

int main(void)
{
    cin >> a >> b >> mod;
    long long ans;
    while(b)
    {
        if(b&1) ans = (ans + a) % mod;
        a = a * 2 % mod;
        b >>= 1;
    }
    cout << ans << endl;

    return 0;
}