【题解】UVA10140 [Prime Distance]

【题解】UVA10140 Prime Distance

哈哈哈哈\(miller-rabbin\)水过去了哈哈哈

还能怎么办呢？\(miller-rabbin\)直接搞。枚举即可，还跑得飞快。

当然此题由于\(20000^2 >2^{31}\)，直接预处理\(20000\)内的质数就好了

放mr的代码

#include<bits/stdc++.h>

using namespace std;typedef long long ll;

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define RP(t,a,b)  for(register int t=(a),edd=(b);t<=edd;++t)

#define ERP(t,a)   for(register int t=head[a];t;t=e[t].nx)

#define midd register int mid=(l+r)>>1

#define TMP template < class ccf >

#define lef l,mid,pos<<1

#define rgt mid+1,r,pos<<1|1

#define pushup(pos) (seg[pos]=seg[pos<<1]+seg[pos<<1|1])

TMP inline ccf qr(ccf b){

    register char c=getchar();register int q=1;register ccf x=0;

    while(c<48||c>57)q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)x=x*10+c-48,c=getchar();

    return q==-1?-x:x;}

TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}

TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}

TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}

TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}

TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}

//----------------------template&IO---------------------------

#define int long long

inline int ksm(ll base,ll p,ll mod){register int ret=1;base%=mod;

    for(register ll t=p;t;t>>=1,(base*=base)%=mod) if(t&1) (ret*=base)%=mod;

    return ret%mod;

}

inline bool T(int base,int p){

    for(register int t=p-1,sav;t;t>>=1){

	sav=ksm(base,t,p);

	if(sav!=1&&sav!=p-1) return 0;

	if((t&1)||sav==p-1) return 1;

    }return 1;

}

inline bool mb(int x){

    if(x==2||x==3||x==13||x==17) return 1;

    if(x==1) return 0;

    return  T(2,x)&&T(3,x)&&T(13,x)&&T(17,x);

}

int L,R,last,Mx,Mn,ans1,ans2,ans3,ans4;

main(){

    while(cin>>L>>R){

	Mx=0;

	Mn=R-L+2;last=R+1;

	RP(t,L,R) if(mb(t)){ last=t; break;}

	if(last==R+1) {printf("There are no adjacent primes\n"); continue;}

	RP(t,last+1,R){

	    if(mb(t)){

		if(t-last>Mx) Mx=t-last,ans3=last,ans4=t;

		if(t-last<Mn) Mn=t-last,ans1=last,ans2=t;

		last=t;

	    }

	}

	if(Mx==0||Mn==R-L+2) printf("There are no adjacent primes.\n");

	else printf("%d,%d are closest, %d,%d are most distant.\n",ans1,ans2,ans3,ans4);

    }

    return 0;

}

巴特西

【题解】UVA10140 [Prime Distance]

【题解】UVA10140 Prime Distance

最新文章

热门文章