本题有超过范围的数据。
//Code by __dest__ruct__or__(uid=592238)
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define umap unordered_map
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
namespace mySTL{
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline int abs(int a){return a<0?-a:a;}
inline int read(){char c=getchar();int f=1,ans=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9')ans*=10,ans+=c-'0',c=getchar();
return ans*f;}
inline long long readll(){char c=getchar();long long f=1,ans=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9')ans*=10,ans+=c-'0',c=getchar();
return ans*f;}
inline void swap(int &a,int &b){a^=b,b^=a,a^=b;}
inline void write(int x){if(x<0){putchar('-');x=-x;}
if(x>=10){write(x/10);}putchar(x%10+'0');}
inline void writell(long long x){if(x<0){putchar('-');x=-x;}
if(x>=10){writell(x/10);}putchar(x%10+'0');}
inline ll pw(ll a,ll b,ll p){if(b==0)return 1;
if(b==1)return a;
ll mid=pw(a,b/2,p)%p;
if(b&1)return mid*mid%p*a%p;else{return mid*mid%p;}}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
}
using namespace mySTL;
const int cnt=5;
ll exmul(ll n,ll m,ll p){
ll ans=0;
while(m){
if(m&1){
ans=(ans+n)%p;
}
m>>=1;
n=(n+n)%p;
}
return ans;
}
ll expow(ll n,ll m,ll p){
ll ans=1;
while(m){
if(m&1){
ans=exmul(ans,n,p);
}
m>>=1;
n=exmul(n,n,p);
}
return ans;
}
bool Miller_Rabin(ll n){
if(n%2==0||n<3){
return n==2;
}
ll u=n-1,t=0;
while(!(u&1)){
u>>=1;
t++;
}
for(int i=0;i<cnt;i++){
ll a=rand()%(n-2)+2;
ll v=expow(a,u,n);
if(v==1){
continue;
}
ll s=0;
for(;s<t;s++){
if(v==n-1){
break;
}
v=exmul(v,v,n);
}
if(s==t){
return false;
}
}
return true;
}
int l,r,ans;
int main(void){
//freopen("data.txt","r",stdin);
srand(time(0));
l=read();
r=read();
if(r<l){
swap(l,r);
}
if(r>=1000000){
return -1;
}
for(int i=l;i<=r;i++){
ans+=Miller_Rabin(i);
}
write(ans);
return 0;
}
这是测试代码,如果出现了大于 106 的数,那么就会让评测机 RE。
结果真 RE 了。