描述

求 a 乘 b 对 p 取模的值,其中 1≤a,b,p≤10^18。

输入格式

第一行a,第二行b,第三行p。

输出格式

一个整数,表示a*b mod p的值。

样例输入

2
3
9

样例输出

6

解题思路:

我们可以通过类似快速幂的方法解决这个问题。

首先b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+…+c_02^0

那么a * b=a * c_{k-1}2^{k-1}+ a * c_{k-2}2^{k-2}+…+ a * c_02^0

我们就可以通过位运算解决这个问题了。

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
ll mul(ll a,ll b,ll p){
    ll ret=0;
    for(;b;b>>=1,a=a*2%p)
        if(b&1)ret=(ret+a)%p;
    return ret;
}
int main(){
    ll a=read(),b=read(),p=read();
    write(mul(a,b,p));
    return 0;
}

发表评论