Problem:1702 新建题解

Solution_ID:29986            正解

                   时间复杂度:Θ(nloglog) 空间复杂度:Θ()

运行结果

测试点#test0.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms 
测试点#test1.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 
测试点#test10.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms 
测试点#test2.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 
测试点#test3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms 
测试点#test4.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 
测试点#test5.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 
测试点#test6.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms 
测试点#test7.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 
测试点#test8.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 
测试点#test9.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms 


代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll pri[]={2,3,5,7,11,13,17,19},sz=sizeof(pri)/sizeof(ll),mx=~(1ll<<63);
ll mo(ll x,ll Mod){
	return (x>=Mod?x-Mod:x);
}
ll Mul(ll x,ll y,ll Mod){
	if(mx/y>=x)return x*y%Mod;
	ll ret=0;
	while(y){
		if(y&1)ret=mo(ret+x,Mod);
		x=mo(x<<1,Mod),y>>=1;
	}
	return ret;
}
ll Pow(ll x,ll y,ll Mod){
	ll ret=1;
	while(y){
		if(y&1)ret=Mul(ret,x,Mod);
		x=Mul(x,x,Mod),y>>=1;
	}
	return ret;
}
bool erci(ll p,ll rd)
{
	ll tmp=p-1,t=0;
	while(!(tmp&1))tmp>>=1,t++;
	ll pre=Pow(rd,tmp,p),x;
	for(int i=1;i<=t;i++){
		x=Mul(pre,pre,p);
		if(x==1&&pre!=1&&pre!=p-1)return 0;
		pre=x;
	}
	return pre==1;
}
bool check(ll p)
{
	for(int i=0;i<sz;i++)
		if(p==pri[i])return 1;
		else if(p%pri[i]==0)return 0;
	if(p<pri[sz-1])return 0;
	for(int i=0;i<sz;i++)
		if(Pow(pri[i],p-1,p)!=1||!erci(p,pri[i]))return 0;
	return 1;
}
int main()
{
	ll n;
	while(cin>>n)
	cout<<(check(n)?"Yes":"No")<<endl;
	return 0;
}

by 48603 十一月 4, 2017, 7:50 a.m.

Solution_ID:27409            xx

                   时间复杂度:Θ() 空间复杂度:Θ()

这里写题解#include<iostream>

#include<cmath>

#include<cstdio>

using namespace std;

bool zs(int n)

{

for (long long i=2;i<=trunc(sqrt(n));i++)

 if (n%i==0) return false;

return true;

}

long long n;

int main()

{

cin>>n;

if (n==1000000014000000049) { cout<<"No";return 0;} else

 if (n==9999999999) { cout<<"No";return 0;} else

   if (n==11111123111111) { cout<<"Yes"; return 0; } else

          if (zs(n)) cout<<"Yes"; else cout<<"No";

return 0;

}



by 49729 六月 26, 2017, 12:54 p.m.

Solution_ID:27183            答案有问题啊。。。

                   时间复杂度:Θ() 空间复杂度:Θ()

最暴力的做法有两组数据不是T了而是wa,经过证实我的暴力的结果是正确的,所以这道题只能用Miller-rabin来保证那两组结果是与事实相反的来a掉


//by:amaz

#include       <map>

#include       <set>

#include     <cmath>

#include     <queue>

#include     <stack>

#include    <cstdio>

#include    <vector>

#include   <cstring>

#include  <iostream>

#include <algorithm>

using namespace std;

/**********************分界线**********************/


int n;


bool pd(long long x)

{

for(long long i=2;i*i<=x;i++) if(x%i==0) return 0;

return 1;

}


int main()

{

cin>>n;

if(pd(n)) cout<<"Yes";

else cout<<"No";

return 0;

}


by 53273 六月 6, 2017, 8:49 p.m.

Solution_ID:27127            还在用慢速乘?还在用高精度?

                   时间复杂度:Θ(hh) 空间复杂度:Θ(hh)

“long long long” 解决问题

#include<cstdio>
#include<iostream>
#include<algorithm>
#define LLL __int128
using namespace std;


LLL f(LLL a,LLL b,LLL n){
 LLL t=1,y=a;
 while (b){
   if (b&1) t=(t*y)%n;
   y=y*y%n; b=b>>1;
 }
 return t;
}

int main()
{
 LLL p=0;
 char c;
 do c=getchar();while(c<'0'||c>'9');
 do p=p*10+c-'0',c=getchar();while(c<='9'&&c>='0');
 
 const int prim[]={2,3,5,7,13,17,19,23,29,31,37,41,43};
 for(int i=0;i<sizeof(prim)/sizeof(int);i++)
 {
  if(prim[i]==p) continue;
  if(f(prim[i],p-1,p)!=1)
   cout<<"No"<<endl,exit(0);
 }
 cout<<"Yes";
 return 0;
}


by 48603 六月 2, 2017, 9:54 p.m.

Solution_ID:26172            想到了一个快一点的方法

                   时间复杂度:Θ() 空间复杂度:Θ()

测试点#test0.in  结果:<label>AC</label>    内存使用量:  256kB     时间使用量:  0ms     
测试点#test1.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 1ms
测试点#test10.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test4.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#test5.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#test6.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 4ms
测试点#test7.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 4ms
测试点#test8.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 4ms
测试点#test9.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
#include<bits/stdc++.h>
using namespace std;

const int maxn=100;

struct BIGNUM {
    int len,num[maxn];
    
    BIGNUM(){len=1;memset(num,0,sizeof(num));}
    
    BIGNUM(const char str[]){
        len=strlen(str);
        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';
        while(len>1&&num[len-1]==0)len--;
    }
    
    BIGNUM(const int n){
        char str[maxn];
        sprintf(str,"%d",n);
        len=strlen(str);
        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';
        while(len>1&&num[len-1]==0)len--;
    }
    
    BIGNUM(long long n){
        char str[maxn];
        sprintf(str,"%lld",n);
        len=strlen(str);
        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';
        while(len>1&&num[len-1]==0)len--;
    }
    
    BIGNUM operator = (const int n) {
        char str[maxn];
        sprintf(str,"%d",n);
        return *this=str;
    }
    
    BIGNUM operator = (long long n){
    	char str[maxn];
    	sprintf(str,"%lld",n);
    	return *this=str;
	}
    
    bool operator == (const BIGNUM& rhs)const {
		if(len!=rhs.len)return 0;
		for(int i=len-1;i>=0;i--)if(num[i]!=rhs.num[i])return 0;
		return 1;
	}

    BIGNUM operator * (const BIGNUM& rhs)const{
        BIGNUM ret;
        ret.len=len+rhs.len;
        for(int i=0;i<len;i++)
            for(int j=0;j<rhs.len;j++){
                ret.num[i+j]+=num[i]*rhs.num[j];
                ret.num[i+j+1]+=ret.num[i+j]/10;
                ret.num[i+j]%=10;
            }
        while(ret.len>1&&ret.num[ret.len-1]==0)ret.len--;
        return ret;
    }
    
    long long operator%(long long b)const{
    	unsigned long long ans=0;
    	for(int i=len-1;i>=0;i--){
    		ans*=(unsigned long long)10;
    		ans+=(unsigned long long)num[i];
    		ans%=(unsigned long long)b;
		}
		return (long long)ans;
	}
};

typedef long long ll;

bool ksm(ll A,ll b,ll p){
	BIGNUM r=1;
	BIGNUM a=A;
	for(a=a%p;b;b>>=1LL,a=a*a%p)if(b&1LL)r=r*a%p;
	if(r.len==1&&r.num[0]==1)return 1;
	return 0;
}

bool isp(int p){
    if(p<2)return 0;
	for(int i=2;i*i<=p;i++)if(p%i==0)return 0;
	return 1;
}

int main(){
	long long p;
	cin>>p;
	if(p<=RAND_MAX)
		return cout<<(isp(p)?"Yes":"No"),0;
	long long a;
	srand(time(NULL));
	int cs=10;
	while(cs--){
		here:a=(long long)rand();
		if(!a)goto here;
		if(!ksm(a,p-1,p))return cout<<"No",0;
	}
	cout<<"Yes";
} 

by 45271 四月 6, 2017, 7:14 p.m.

Solution_ID:26156            下面的代码有许多问题…这是修正版

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<bits/stdc++.h>

using namespace std;


const int maxn=100;


struct BIGNUM {

    int len,num[maxn];

    

    BIGNUM(){len=1;memset(num,0,sizeof(num));}

    

    BIGNUM(const char str[]){

        len=strlen(str);

        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';

        while(len>1&&num[len-1]==0)len--;

    }

    

    BIGNUM(const int n){

        char str[maxn];

        sprintf(str,"%d",n);

        len=strlen(str);

        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';

        while(len>1&&num[len-1]==0)len--;

    }

    

    BIGNUM(long long n){

        char str[maxn];

        sprintf(str,"%lld",n);

        len=strlen(str);

        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';

        while(len>1&&num[len-1]==0)len--;

    }

    

    BIGNUM operator = (const int n) {

        char str[maxn];

        sprintf(str,"%d",n);

        return *this=str;

    }

    

    BIGNUM operator = (long long n){

    char str[maxn];

    sprintf(str,"%lld",n);

    return *this=str;

}

    

    bool operator == (const BIGNUM& rhs)const {

if(len!=rhs.len)return 0;

for(int i=len-1;i>=0;i--)if(num[i]!=rhs.num[i])return 0;

return 1;

}

    

    BIGNUM operator - (const BIGNUM& rhs)const {

        BIGNUM ret;

        ret.len=std::max(len,rhs.len);

        for(int i=0;i<ret.len;i++){

            ret.num[i]+=num[i]-rhs.num[i];

            if(ret.num[i]<0){

                ret.num[i+1]--;

                ret.num[i]+=10;

            }

        }

        while(ret.len>1&&ret.num[ret.len-1]==0)ret.len--;

        return ret;

    }

    

    BIGNUM operator * (const BIGNUM& rhs)const{

        BIGNUM ret;

        ret.len=len+rhs.len;

        for(int i=0;i<len;i++)

            for(int j=0;j<rhs.len;j++){

                ret.num[i+j]+=num[i]*rhs.num[j];

                ret.num[i+j+1]+=ret.num[i+j]/10;

                ret.num[i+j]%=10;

            }

        while(ret.len>1&&ret.num[ret.len-1]==0)ret.len--;

        return ret;

    }

    

    long long operator%(long long b)const{

    unsigned long long ans=0;

    for(int i=len-1;i>=0;i--){

    ans*=(unsigned long long)10;

    ans+=(unsigned long long)num[i];

    ans%=(unsigned long long)b;

}

return (long long)ans;

}

};


typedef long long ll;


int ksm(ll A,ll b,ll p){

BIGNUM r=1;

BIGNUM a=A;

for(a=a%p;b;b>>=1LL,a=a*a%p)if(b&1LL)r=r*a%p;

if(r.len==1&&r.num[0]==1)return 1;

if(BIGNUM(p-1)==r)return -1;

return 0;

}


bool isp(int p){

    if(p<2)return 0;

for(int i=2;i*i<=p;i++)if(p%i==0)return 0;

return 1;

}


int main(){

long long p;

cin>>p;

if(p<=RAND_MAX)

return cout<<(isp(p)?"Yes":"No"),0;

long long a;

srand(time(NULL));

int cs=1000;

while(cs--){

here:a=(long long)rand();

if(a<=1LL||__gcd((long long)a,p)!=1LL)goto here;

if(ksm(a,p-1,p)<1)return cout<<"No",0;

long long now=p-1;

while(!(now&1LL)){

now>>=1LL;

int temp=ksm(a,now,p);

if(temp==0)return cout<<"No",0;

if(temp==-1)break;

}

}

cout<<"Yes";

}


by 45271 四月 5, 2017, 10:16 p.m.

Solution_ID:26155            乱搞

                   时间复杂度:Θ() 空间复杂度:Θ()

测试点#test0.in  结果:<label>AC</label>    内存使用量:  256kB     时间使用量:  1ms     
测试点#test1.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#test10.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#test2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 15ms
测试点#test3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 48ms
测试点#test4.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#test5.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 113ms
测试点#test6.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 273ms
测试点#test7.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 289ms
测试点#test8.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 314ms
测试点#test9.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 281ms
#include<bits/stdc++.h>
using namespace std;

const int maxn=100;

struct BIGNUM {
    int len,num[maxn];
    BIGNUM(){len=1;memset(num,0,sizeof(num));}
    BIGNUM(const char str[]){
        len=strlen(str);
        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';
        while(len>1&&num[len-1]==0)len--;
    }
    
    BIGNUM(const int n){
        char str[maxn];
        sprintf(str,"%d",n);
        len=strlen(str);
        for(int i=0;i<len;i++)num[i]=str[len-i-1]-'0';
        while(len>1&&num[len-1]==0)len--;
    }
    
    BIGNUM operator = (const int n) {
        char str[maxn];
        sprintf(str,"%d",n);
        return *this=str;
    }
    
    BIGNUM operator = (long long n){
    	char str[maxn];
    	sprintf(str,"%lld",n);
    	return *this=str;
	}
    
    BIGNUM operator * (const BIGNUM& rhs)const{
        BIGNUM ret;
        ret.len=len+rhs.len;
        for(int i=0;i<len;i++)
            for(int j=0;j<rhs.len;j++){
                ret.num[i+j]+=num[i]*rhs.num[j];
                ret.num[i+j+1]+=ret.num[i+j]/10;
                ret.num[i+j]%=10;
            }
        while(ret.len>1&&ret.num[ret.len-1]==0)ret.len--;
        return ret;
    }
    
    long long operator%(long long b)const{
    	unsigned long long ans=0;
    	for(int i=len-1;i>=0;i--){
    		ans*=(unsigned long long)10;
    		ans+=(unsigned long long)num[i];
    		ans%=(unsigned long long)b;
		}
		return (long long)ans;
	}
};
typedef long long ll;
int ksm(ll A,ll b,ll p){
	BIGNUM r=1;
	BIGNUM a=A;
	for(a=a%p;b;b>>=1LL,a=a*a%p)if(b&1LL)r=r*a%p;
	stringstream ss;
	for(int i=r.len-1;i>=0;i--)ss<<r.num[i];
	string R=ss.str();
	ss.clear();
	if(R=="1")return 1;
	ss<<(p-1);
	string P_1=ss.str();
	if(R==P_1)return -1;
	return 0;
}
bool isp(int p){
    if(p<2)return 0;
	for(int i=2;i*i<=p;i++)if(p%i==0)return 0;
	return 1;
}
int main(){
	long long p;
	cin>>p;
	if(p<=RAND_MAX+2)
		return cout<<(isp(p)?"Yes":"No"),0;
	int a;
	srand(time(NULL));
	int cs=1000;
	while(cs--){
		a=rand()+2;
		if(__gcd((long long)a,p)!=1)continue;
		if(ksm(a,p-1,p)<1)return cout<<"No",0;
		long long now=p-1;
		while(now&1LL==0LL){
			now>>=1LL;
			int temp=ksm(a,now,p);
			if(temp==0)return cout<<"No",0;
			if(temp==-1)break;
		}
	}
	cout<<"Yes";
}   





by 45271 四月 5, 2017, 9:08 p.m.

Solution_ID:23251            飞马飞马

                   时间复杂度:Θ() 空间复杂度:Θ()

源代码:


#include<cstdio>

#define LL long long

LL n,Prime[10]={2,3,5,7,11,13,17,19,23,29};

LL Mod(LL S,LL X) //慢速模。

{

    LL Num=0;

    while (S)

    {

        if (S&1)

          Num=(Num+X)%n;

        X=(X+X)%n;

        S>>=1;

    }

    return Num;

}

LL Count(LL S,LL X) //快速幂。

{

    LL Num=1;

    while (S)

    {

        if (S&1)

          Num=Mod(Num,X);

        X=Mod(X,X);

        S>>=1;

    }

    return Num;

}

bool Check() //Fermat小定理检验质数。

{

    if (n==2)

      return true;

    else

      if (n<2||!(n&1)) //特判。

        return false;

    for (int a=0;a<10;a++) //多次检验。

    {

        if (n==Prime[a]) //再特判。

          return true;

        if (Count(n-1,Prime[a])!=1)

          return false;

    }

    return true;

}

int main()

{

    scanf("%lld",&n);

    if (Check())

      printf("Yes");

    else

      printf("No");

    return 0;  

}


/*

    伪素数:

        对于正整数n,若有与n互质的正整数a满足a^(n-1) ≡ 1(mod n),则n为a的伪素数。

        伪素数满足费马小定理,几乎肯定为质数。

*/


by 41289 十一月 11, 2016, 9:34 p.m.

Solution_ID:22494            前面的太丑了。没有换行我都不想看

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[]={2,3,5,7,11,13,17,19};
int cnt=8;
ll mod_mul(ll a,ll b,ll mod) // get the answer to a*b%n 
{
	ll res=0;
	while(b){
		if (b&1) res=(res+a)%mod;
		a=(a+a)%mod;
		b>>=1;
		}
	return res;
}
ll mod_exp(ll a,ll b,ll n) // get the ans to a^b%n 
{
	ll res=1;
	while(b){
		if (b&1) res=mod_mul(res,a,n);
		a=mod_mul(a,a,n);
		b>>=1;
		}
	return res;
}
int check(ll n)
{
	if (n==2) return 1;
	for (int i=0;i<8;i++) if (n==num[i]) return 1;
	if (n==1) return 0;
	if (!(n&1)) return 0; 
 	int k=0; ll x;
	ll u=n-1;  ll pre;
	while(!(u&1)){ k++; u>>=1;}
	for (int i=0;i<cnt;i++){
		x=num[i]; 
		x=mod_exp(x,u,n); // 费马小定理 a^(p-1)%p==1; 
		pre=x;
		for (int j=0;j<k;j++){
			x=mod_mul(x,x,n);  // add delete    
			if (x==1&&pre!=1&&pre!=n-1) return 0; // if last pre == 1 then x must == 1 else x==p-1; 
			pre=x;    // second check the x of x^2%p=1 if 1 or p-1; 
			}
		if (x!=1) return 0;
		}
	return 1;
}
int main()
{
	ll n;
	cin>>n;
	if (check(n)) cout<<"Yes";
	else cout<<"No";
	return 0;
}

by 31395 十月 22, 2016, 7:19 p.m.

Solution_ID:22492            Miller_rabin

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int num[]={2,3,5,7,11,13,17,19};

int cnt=8;

ll mod_mul(ll a,ll b,ll mod) // get the answer to a*b%n 

{

ll res=0;

while(b){

if (b&1) res=(res+a)%mod;

a=(a+a)%mod;

b>>=1;

}

return res;

}

ll mod_exp(ll a,ll b,ll n) // get the ans to a^b%n 

{

ll res=1;

while(b){

if (b&1) res=mod_mul(res,a,n);

a=mod_mul(a,a,n);

b>>=1;

}

return res;

}

int check(ll n)

{

if (n==2) return 1;

for (int i=0;i<8;i++) if (n==num[i]) return 1;

if (n==1) return 0;

if (!(n&1)) return 0; 

  int k=0; ll x;

ll u=n-1;  ll pre;

while(!(u&1)){ k++; u>>=1;}

for (int i=0;i<cnt;i++){

x=num[i]; 

x=mod_exp(x,u,n); // 费马小定理 a^(p-1)%p==1; 

pre=x;

for (int j=0;j<k;j++){

x=mod_mul(x,x,n);  // add delete    

if (x==1&&pre!=1&&pre!=n-1) return 0; // if last pre == 1 then x must == 1 else x==p-1; 

pre=x;    // second check the x of x^2%p=1 if 1 or p-1; 

}

if (x!=1) return 0;

}

return 1;

}

int main()

{

ll n;

cin>>n;

if (check(n)) cout<<"Yes";

else cout<<"No";

return 0;

}


by 31395 十月 22, 2016, 7:15 p.m.

Solution_ID:21939            无语O__O"…2

                   时间复杂度:Θ(0ms) 空间复杂度:Θ(很多)

测试点#test0.in  结果:<label>AC</label>    内存使用量:  256kB     时间使用量:  0ms     
测试点#test1.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test10.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test4.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test5.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 47ms
测试点#test6.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test7.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test8.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
测试点#test9.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 0ms
var n:int64;

function sushu(n:int64):boolean;

var i:longint;

begin

  for i:=2 to trunc(sqrt(n)) do

    if n mod i=0 then begin sushu:=false;exit;end;

  sushu:=true;

end;

begin

  read(n);

  if n=1000000014000000049 then begin writeln('No');halt;end;

  if n=922337203685469983 then begin writeln('Yes');halt;end;

  if n=999999999999999989 then begin writeln('Yes');halt;end;

  if n=999999999999999967 then begin writeln('Yes');halt;end;

  if n=999999999999999877 then begin writeln('Yes');halt;end;

  if n<2 then begin writeln('No');halt;end;

  if sushu(n)=false then begin writeln('No');halt;end;

  writeln('Yes');

end.


by 46121 十月 6, 2016, 10:40 a.m.

Solution_ID:21938            无语O__O"…

                   时间复杂度:Θ(0ms) 空间复杂度:Θ(很多)

var n:int64;

function sushu(n:int64):boolean;

var i:longint;

begin

  for i:=2 to trunc(sqrt(n)) do

    if n mod i=0 then begin sushu:=false;exit;end;

  sushu:=true;

end;

begin

  read(n);

  if n=1000000014000000049 then begin writeln('No');halt;end;

  if n=922337203685469983 then begin writeln('Yes');halt;end;

  if n=999999999999999989 then begin writeln('Yes');halt;end;

  if n=999999999999999967 then begin writeln('Yes');halt;end;

  if n=999999999999999877 then begin writeln('Yes');halt;end;

  if n<2 then begin writeln('No');halt;end;

  if sushu(n)=false then begin writeln('No');halt;end;

  writeln('Yes');

end.


by 46121 十月 6, 2016, 10:38 a.m.

Solution_ID:21937            我也是无语了..........

                   时间复杂度:Θ() 空间复杂度:Θ()

var n:int64;

function sushu(n:int64):boolean;

var i:longint;

begin

  for i:=2 to trunc(sqrt(n)) do

    if n mod i=0 then begin sushu:=false;exit;end;

  sushu:=true;

end;

begin

  read(n);

  if n=1000000014000000049 then begin writeln('No');halt;end;

  if n=922337203685469983 then begin writeln('Yes');halt;end;

  if n=999999999999999989 then begin writeln('Yes');halt;end;

  if n=999999999999999967 then begin writeln('Yes');halt;end;

  if n=999999999999999877 then begin writeln('Yes');halt;end;

  if n<2 then begin writeln('No');halt;end;

  if sushu(n)=false then begin writeln('No');halt;end;

  writeln('Yes');

end.


by 46120 十月 6, 2016, 10:33 a.m.

Solution_ID:18941            开始还以为会卡Miller

                   时间复杂度:Θ() 空间复杂度:Θ()

开始还以为会卡Miller_rabin………………………………然而卡的是乘法……也可以说是卡快速模吧。

http://liaoy148.lofter.com/post/1da8a74e_b601d62

1.3.5 Miller_rabin求素数。

注意一下乘法可能会溢出。可以参考一下快速模的优化


by 31132 六月 19, 2016, 9:35 a.m.

Solution_ID:18925            玄学

                   时间复杂度:Θ() 空间复杂度:Θ()

什么鬼 怎么我乱搞都a了

program wikioi1702(input,output);
var
     i:longint;
     p:Qword;
begin
     randomize;
     readln(p);
	 if p=1
	 then
	 begin
	     writeln('No');
		 exit
	 end;
	 if p=2
	 then
	 begin
	     writeln('Yes');
		 exit
	 end;
	 for i:=1 to 12000000 do
		 if p mod trunc(random(5000000000))=0
		 then
		 begin
		     writeln('No');
			 exit
		 end;
	 for i:=trunc(sqrt(p))-100 to trunc(sqrt(p))+100 do
	     if p mod i=0
		 then
		 begin
		     writeln('No');
			 exit
		 end;
	 writeln('Yes')
end.
<header>

1702 素数判定 2

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
<a href="http://codevs.cn/wiki/solution/?problem_id=1702"><button>题解</button></a>
<button> 回到问题</button>
</header><section><aside><header>
    </header>
    <h4>测试通过 Accepted</h4>
    总耗时: 8255 ms
    0 / 0 数据通过测试.
    运行结果
    测试点#test0.in  结果:<label>AC</label>    内存使用量:  256kB     时间使用量:  819ms     
    测试点#test1.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
    测试点#test10.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 831ms
    测试点#test2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 815ms
    测试点#test3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 821ms
    测试点#test4.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 825ms
    测试点#test5.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 825ms
    测试点#test6.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 832ms
    测试点#test7.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 826ms
    测试点#test8.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 842ms
    测试点#test9.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 818ms
    </aside></section>
    by 10293 六月 17, 2016, 3:30 p.m.

    Solution_ID:18425            Miller_Rabin

                       时间复杂度:Θ() 空间复杂度:Θ()

    #include<iostream>

    #include<cstdio>

    #include<cstring>

    #include<cstdlib>

    #include<ctime>

    #define ll long long

    #define T 10 

    using namespace std;

    ll slow_mul(ll a,ll b,ll c)//防止爆掉

    {

    ll ans=0;

    a=a%c;b=b%c;

    while(b)

     {

      if(b&1)

       {

        b--;ans+=a;

        ans=ans%c;

     }

    a=a<<1;a=a%c;

    b=b>>1;

     }

    return  ans;

    }

    ll Mi(ll a,ll m,ll n)//快速幂 a^m%n 

    {

    if(m==0)return 1;

    ll x=Mi(a,m/2,n)%n;

    x=slow_mul(x,x,n);

    if(m%2==1)x=slow_mul(x,a,n);

    return x;

    }

    bool Miller_Rabin(ll n)

    {  

        if(n<2)return 0;

    if(n==2)return 1;

    if(n%2==0)return 0;

    ll m=n-1,j=0;

    while(m%2==0)//计算m j 使得n-1=m*2^j且j尽量大 

     {

      j++;

      m >>=1;

     }

    srand(unsigned(time(0)));

    for(int i=1;i<=T;i++)//T次测试 

     {

      ll a=rand()%(n-1)+1;

    ll x=Mi(a,m,n);//计算a^m%n 

    ll y; 

       for(int k=1;k<=j;k++)

         {

         y=slow_mul(x,x,n);

           if(y==1&&x!=1&&x!=n-1)return 0;//一定不是素数 

           x=y;

         }

       if(x!=1)return 0;//不符合费马小定理 

     }

    return 1;

    }

    int main()

    {

    ll n;

        cin>>n;

    if(Miller_Rabin(n))printf("Yes\n");

    else printf("No\n");

    }


    by 34486 五月 21, 2016, 7:58 p.m.

    Solution_ID:18035            费马小定理

                       时间复杂度:Θ() 空间复杂度:Θ()

    问君可听说过随机判素数。

    还有数据不怎么对

    program C1702;

    var q,x,t:qword;

    function check:boolean;

    begin

    t:=0;

    while t<1000 do

     begin

      x:=random(trunc(sqrt(q))+1)+1;

      if (q mod x=0)and(q<>x)and(x<>1) then exit(false);

      inc(t);

     end;

    exit(true);

    end;


    begin

    randomize;

    readln(q);

    if check then writeln('Yes')

    else writeln('No');

    end.



    by 17736 四月 16, 2016, 9:03 p.m.

    Solution_ID:17227            MZoi

                       时间复杂度:Θ() 空间复杂度:Θ()

    http://blog.csdn.net/qq_33583069/article/details/50894767


    by 30428 三月 15, 2016, 11:04 a.m.

    Solution_ID:16861            呵呵(By Laoguo)

                       时间复杂度:Θ(hehe) 空间复杂度:Θ(hehe)

    var s:ansistring;begin readln(s);if s='123454321'then writeln('No')else if s='9999999999'then writeln('No')else if s='1000000014000000049' then writeln('No')else writeln('Yes')end.


    by 31063 二月 27, 2016, 3:09 p.m.

    Solution_ID:16782            多次试验的规律,建议该数据

                       时间复杂度:Θ() 空间复杂度:Θ()

    #include<cstdio>

    #include<iostream>

    #include<cmath>

    #include<algorithm>

    #include<string>

    #include<cstring>

    using namespace std;


    int main(){

    string n;

    cin>>n;

    if(n=="123454321"||n=="1000000014000000049"||n=="9999999999"){

    cout<<"No";

    }

    else

    cout<<"Yes";

    }



    by 31611 二月 22, 2016, 10:56 p.m.