位运算

1. a^b

求 a 的 b 次方对 p 取模的值。

输入格式 三个整数 a,b,p ,在同一行用空格隔开。

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

数据范围 0≤a,b,p≤109 数据保证 p≠0 输入样例：

3 2 7

输出样例：

2

#include <bits/stdc++.h> using namespace std; int ebs(int a,int b,int p){ int sum=1%p; while(b){ if(b%2) sum=sum*1ll*a%p; b=b/2; a=a*1ll*a%p; } return sum; } int main() { int a,b,p; cin>>a>>b>>p; cout<<ebs(a,b,p)<<endl; }

标签 快速幂 细节 防止溢出，在运算过程中乘1ll转换成long long类型

2.64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式 第一行输入整数a，第二行输入整数b，第三行输入整数p。

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

数据范围 1≤a,b,p≤1018 输入样例：

3 4 5

输出样例：

2

#include <bits/stdc++.h> using namespace std; typedef long long ull; int main() { ull a,b,p; cin>>a>>b>>p; ull sum=0; while(b){ if(b%2) sum=(sum+a)%p; b=b/2; a=a*2%p; } cout<<sum<<endl; }

思路 乘积过大，利用位运算转化成相加的思想