算法竞赛进阶指南0x00基本算法 0x01位运算 例题a*b%p

题目

求 a 乘 b 对 p 取模的值。

输入格式

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

输出格式

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

数据范围

1≤a,b,p≤1018

输入样例：

3

4

5

输出样例：

2

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long a=sc.nextLong();
		long b=sc.nextLong();
		long p=sc.nextLong();
		long res=0;
		long k=a;
		while(b>0) {
			if((b&1)==1) {//b是奇数
				res+=k;
				res%=p;
			}
			k=2*k;
			k%=p;//乘数取模对结果无影响
			b=b>>1;
		}
		res%=p;
		System.out.println(res);
	}}