Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

对拍了两千组范围内的随机数据都过了 包括discuss里的,还是wa...,哪位大佬给看看吖

Posted by 918106840125 at 2019-07-11 12:03:15 on Problem 2689
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=100000;
int prime[maxn],v[maxn],m;
bool nt_prime[10*maxn+5];
ll tmp[maxn*10+5];
void primes(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(v[i]==0)
		{
			prime[++m]=i;
			v[i]=i;
		}
		for(int j=1;j<=m;j++)
		{
			if(prime[j]>v[i]||prime[j]>n/i)break;
			v[prime[j]*i]=prime[j];
		}
	}
}
int main()
{
	//freopen("E:\\duipai\\in.txt","r",stdin);
	//freopen("E:\\duipai\\out.txt","w",stdout);
	ll l,r;
	while(~scanf("%lld%lld",&l,&r)){
	m=0;
	memset(v,0,sizeof(v));
	memset(prime,0,sizeof(prime));
	memset(tmp,0,sizeof(tmp));
	primes((int)sqrt(r));
	memset(nt_prime,0,sizeof(nt_prime));
	for(int i=1;i<=m;i++)
	{
		for(ll j=l/prime[i];j*prime[i]<=r;j++)	
		{
			if(j>1&&j*prime[i]>=l)//防止下标为负 
			nt_prime[j*prime[i]-l]=1;//注意,倍数必须是大于等于二倍来筛素数 
		}
	}
	int cnt=0;
	for(ll i=l;i<=r;i++)
	{
		if(!nt_prime[i-l]&&l!=1)//一定要注意1既不是素数也不是合数,筛的时候从2开始没有把它筛掉 
		{
			tmp[++cnt]=i-l;
		}
	}
	if(cnt<=1)printf("There are no adjacent primes.\n");
	else 
	{
		ll Mdis=0,mdis=r-l+1,head,next,sh,sn,mh,mn;
		for(int i=1;i<cnt;i++)
		{
			head=tmp[i+1];
			next=tmp[i];
			if(Mdis<head-next)	
			{
				Mdis=head-next;
				mh=head,mn=next;
			}
			if(mdis>head-next)
			{
				mdis=head-next;
				sh=head,sn=next;
			}
		}
		printf("%lld,%lld are closest, %lld,%lld are most distant.\n",sn+l,sh+l,mn+l,mh+l);					
	}
	}
	return 0;
 } 
 /*2147000000 2147483647
1 2
2146483648 2147483647
2147483047 2147483647
 */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator