问题来源于:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=609
简单的讲:求解a*b%c 其中0<a,b,c<2^64
分析:这样的式子和a^b%c很像,所以可以用类似于快速幂取模的方法来做。即,将b写成二进制来看,然后拆开相加(正因为二进制的特殊性,才有快速乘和快速幂的成功
32+16+4=52 (实际操作过程中,每次相加都取模)
这一过程和快速幂取模非常相似。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL a,b,c;
LL work(){
LL ans=0;
a=a%c;
b=b%c;
while(b>0){
if(b&1) ans=(ans+a)%c;
a=(a+a)%c;
b>>=1;
}
return ans;
}
int main()
{
while(~scanf("%lld %lld %lld",&a,&b,&c)){
printf("%lld\n",work());
}
return 0;
}
另外,nefu OJ对于long long的输入输出只认%lld,不认%I64d,不要在这点上吃亏!
当然用java也行:
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
BigInteger a,b,c;
Scanner cin=new Scanner(System.in);
String aa,bb,cc;
while(cin.hasNext()){
aa=cin.next();
bb=cin.next();
cc=cin.next();
a=new BigInteger(aa);
b=new BigInteger(bb);
c=new BigInteger(cc);
System.out.println(a.multiply(b).mod(c));
}
}
}
有的对时间要求较高的题会同时应用到快速乘取模和快速幂取模。