0x00 基本算法第二题
算法标签:位运算
来源:《算法竞赛进阶指南》
描述
求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a,第二行输入整数b,第三行输入整数p。
输出格式
输出一个整数,表示a*b mod p
的值。文章来源:https://www.toymoban.com/news/detail-799411.html
数据范围
1≤a,b,p≤10^18文章来源地址https://www.toymoban.com/news/detail-799411.html
输入样例:
3
4
5
输出样例:
2
自用,AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long // define定义
int main()
{
/* 初始化 */
ll a,b,p;
ll res;
/* 读入 */
scanf("%lld %lld %lld", &a, &b ,&p);
/* 快速幂 */
while(b) // 终止条件是b == 0
{
if(b & 1) // 判断二进制下的b的末位01情况
res = (res + a) % p; // 因为是乘,使所以是加上a
b >>= 1; // b整除2
a = a * 2 % p; // a乘上2(因为是二进制)
}
printf("%lld",res);
}
到了这里,关于AcWing:90. 64位整数乘法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!