返回信息流以下代码提交一直是wa，按理说long long的范围比1e18要大，为什么还会wa呢？而且经检测到1e10就测不出来了，哪里溢出了吗？
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
long long Montgomery(long long a,long long b,long long m)
{
long long r=1;
a %=m;
while(b>1)
{
if((b&1)!=0)
r = (r*a)%m;
a = (a*a)%m;
b/=2;
}
return (r*a)%m;
}
bool isPrime(long long n) {
if(n<=2)
return n==2;
else if(n%2==0)
return false;
else {
srand(unsigned(time(0)));
long long u=n-1;
while(u%2==0)
u/=2;
for(int i=1;i<10;i++) {
long long a=(long)(rand()%(n-3)+2);
long long x=Montgomery(a,u,n);
while(u<n) {
long long y=Montgomery(x,x,n);
if(y==1&&x!=1&&x!=n-1)
return false;
x=y;
u*=2;
}
if(x!=1)
return false;
}
return true;
}
}
int main()
{
int t;
long long a[50];
cin>>t;
for(int i=0;i<t;i++) {
cin>>a[i];
if(isPrime(a[i]))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89537同步于 2016/4/5
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[问题]判断一个较大的数(1e18内)是不是质数
lhy963
2016/4/5镜像同步9 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
http://hihocoder.com/contest/hiho92
我这个写的不就是MR测试么.........
【 在 whn6325689 的大作中提到: 】
: 考虑尝试一下，米勒罗宾测试？
: 其实可以给个链接之类的东西？
= =我一开始觉得是
看了半天又否决了，我建议您选择一个看上去好一些的模板（大概指的是不一定要真的随机一个数，可以自己随便搞几个），当然除了这部分我的代码似乎也很丑
我猜你某个地方的乘法爆了long long
代码参见，http://paste.ubuntu.com/15629091/
【 在 lhy963 的大作中提到: 】
: http://hihocoder.com/contest/hiho92
: 我这个写的不就是MR测试么.........