警示后人
查看原帖
警示后人
592238
Elairin176楼主2023/1/22 09:11

本题有超过范围的数据。

//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;
}

这是测试代码,如果出现了大于 10610^6 的数,那么就会让评测机 RE。
结果真 RE 了。

2023/1/22 09:11
加载中...