空中限制,710官方网站标题叙述 Description

1702 素数剖断 二

 

 时限: 1s

 空间限制: 12捌仟KB

 标题等级 : 钻石
Diamond

题解

 

 

 

难点叙述 Description

三个数,他是素数么?

设他为P满足(P<=263-1)

 

输入描述 Input Description

P

出口描述 Output Description

Yes|No

样例输入 Sample Input

2

 

样例输出 Sample Output

Yes

 

数量范围及提醒 Data Size & Hint

算法导论——数论那一节
注意Carmichael Number

 

1702 素数判别 二
光阴限定: 1 s
空中限制: 127000 KB
主题素材等级 : 钻石 Diamond
传送门
难题叙述 Description
二个数,他是素数么?
设他为P满足(P<=263-1)
输入描述 Input Description
P
出口描述 Output Description
Yes|No
样例输入 山姆ple Input
2
样例输出 Sample Output
Yes
数量范围及提醒 Data Size & Hint
算法导论——数论那壹节
注意Carmichael Number
分类标签 Tags
素数推断 数论

170贰 素数推断 二,170二素数剖断

直接推断??? T成狗。。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
long long n;
long long  read()
{
    long long x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
bool pd(long long x)
{
    if(x==1) return false;
    for(long long j=2;j*j<=x;j++)
     if(x%j==0) return false;
    return true;
}
int main()
{
    n=read();
    if(pd(n)) printf("Yes");
    else printf("No");
    return 0;
}
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
LL n;
int s[]={2,3,5,7,11,13,17,19,23,29};
LL slowmi(LL a,LL b)
{
    LL tot=0;
    for(LL i=a;i;i>>=1)
    {
        if(i&1) tot=(tot+b)%n;
        b=(b+b)%n;
    }
    return tot%n;
}
LL mi(LL a,LL b)
{
    LL tot=1;
    for(LL i=a;i;i>>=1)
    {
        if(i&1) tot=slowmi(tot,b)%n;
        b=slowmi(b,b)%n;
    }
    return tot%n;
}
bool check()
{
    if(n==2) return true;
    else if(n<2||!(n&1))  return false;
    for(int i=0;i<10;i++)//费马小定理10次计算 
    {
        if(n==s[i])return true;
        if(mi(n-1,s[i])!=1) return false;
    }
    return true;
}
int main()
{
    cin>>n;
    if(check()) 
      printf("Yes");
    else printf("No");
    return 0;  
}

170二 素数判断 2

 

时限: 1 s
空中限制: 12九千 KB 标题等第 : 钻石 Diamond
      标题叙述 Description

2个数,他是素数么?

设他为P满足(P<=263-1)

 

输入描述 Input Description

P

输出描述 Output Description

Yes|No

样例输入 萨姆ple Input

2

 

样例输出 萨姆ple Output

Yes

 

数据范围及提醒 Data Size & Hint

算法导论——数论那壹节
注意Carmichael Number

瞩目读入的时候不知为啥必须要用cin。。。 (因为自身在前面定义了 ll=long
long =.= 。。。。 。。 。。 那道题重要选拔费马小定律

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<ctime>
 6 #define ll long long int
 7 using namespace std;
 8 ll n;
 9 ll pd[14]={10,35,77,535,71497,2,3,5,7,11,3161};
10 ll fastmul(ll a,ll b)
11 {
12     ll r=0;
13     ll base=a;
14     while(b!=0)
15     {
16         if(b%2!=0)
17         {
18             b--;
19             r=(r+base)%n;
20         }
21         b=b/2;
22         base=(base+base)%n;
23     }
24     return r%n;
25 }
26 ll fastpow(ll a,ll b)
27 {
28     ll r=1;
29     ll base=a;
30     while(b!=0)
31     {
32         if(b%2!=0)
33         r=fastmul(r,base)%n;
34         base=fastmul(base,base)%n;
35         b=b/2;
36     }
37     return r%n;
38 }
39 ll check(ll n)
40 {
41     if(n==2)
42     {
43         return 1;
44     }
45     if(n<2&&(n%2==0))
46     {
47         return 0;
48     }
49     for(ll i=0;i<11;i++)
50     {
51         ll x=pd[i];
52         if(x%n==0)
53         continue;
54         ll ans=fastpow(x,n-1)%n;
55         if(ans!=1)
56         return 0;
57     }
58     return 1;
59 }
60 int main()
61 {
62     //srand(time(0));
63     scanf("%I64d",&n);
64     cin>>n;
65     if(check(n))
66     {
67         printf("Yes");
68     }
69     else
70     {
71         printf("No");
72     }
73     return 0;
74 }

 

http://www.bkjia.com/cjjc/1207896.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1207896.htmlTechArticle1702 素数判断 2,1702素数推断 170二 素数剖断 二时间范围: 一 s 空间范围: 127000 KB 标题品级 : 钻石 Diamond 题目叙述
Description 3个数,他是素数么…

看似要用什么费马小定理的,那就过会在做吧。。。

相关文章