题目描述
求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a,第二行输入整数b,第三行输入整数p。
输出格式
输出一个整数,表示a*b mod p的值。
数据范围
1≤a,b,p≤1018
样例
输入样例:
3
4
5
输出样例:
2
算法1
(快速乘法(倍增思想)) $O()$
时间复杂度
参考文献
python3 代码
def main():
a = int(input())
n = int(input())
MOD = int(input())
res = 0
while n != 0:
if n % 2 == 1:
res = (res + a) % MOD
a = (a + a) % MOD
n >>= 1
print(res)
if __name__ == "__main__":
main()
C++ 代码
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long a; cin >> a;
long long n; cin >> n;
long long MOD; cin >> MOD;
long long res = 0LL;
while (n != 0)
{
if (n % 2 == 1)
{
res = (res + a) % MOD;
}
a = (a + a) % MOD;
n >>= 1;
}
cout << res << endl;
return 0;
}
java 代码
import java.util.Scanner;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
long a = scan.nextLong();
long n = scan.nextLong();
long MOD = scan.nextLong();
//---------------------- 倍增的思想
long res = 0L;
while (n != 0)
{
if (n % 2 == 1)
{
res = (res + a) % MOD;
}
a = (a + a) % MOD;
n >>= 1;
}
System.out.println(res);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla