算法競賽進階指南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);
	}}