各种数论模板 不断更新 绝对精品

1.筛法求素数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=10001;
 7 int vis[MAXN];
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     for(int i=2;i<=sqrt(n);i++)
13     {
14         if(vis[i]==0)
15         {
16             for(int j=i*i;j<=n;j=j+i)
17             {
18                 vis[j]=1;
19             }
20         }
21     }
22     for(int i=2;i<=n;i++)
23     {
24         if(vis[i]==0)
25         printf("%d ",i);
26     }
27     return 0;
28 }

 2.欧几里得求最大公约数及最小公倍数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int gcd(int x,int y)
 7 {
 8     if(y==0)
 9     return x;
10     else
11     return gcd(y,x%y);
12 }
13 int main()
14 {
15     int x,y;
16     scanf("%d%d",&x,&y);
17     int gys=gcd(x,y); 
18     printf("%d\n%d",gys,x*y/gys);
19     
20     return 0;
21 }

 3.扩展欧几里得 求同余方程ax ≡ 1 (mod b)

http://codevs.cn/problem/1200/

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int x,y;
 6 int exgcd(int a,int b,int &x,int &y)
 7 {
 8     if(b==0)
 9     {
10         x=1;
11         y=0;
12         return a;
13     }
14     int r=exgcd(b,a%b,x,y);
15     int tmp=x;
16     x=y;
17     y=tmp-(a/b)*y;
18     return r;
19 }
20 int main()
21 {
22     int a,b;
23     scanf("%d%d",&a,&b);
24     exgcd(a,b,x,y);
25     while(x<0)
26     x=x+b;
27     printf("%d",x);
28     return 0;
29 }

 3.扩展欧几里得 求线性同余方程ax ≡ c (mod b)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int x,y;
 6 int gcd(int a,int b)
 7 {
 8     if(b==0)
 9     return a;
10     else 
11     return gcd(b,a%b);
12 }
13 int exgcd(int a,int b,int &x,int &y)
14 {
15     if(b==0)
16     {
17         x=1;
18         y=0;
19         return a;
20     }
21     int r=exgcd(b,a%b,x,y);
22     int tmp=x;
23     x=y;
24     y=tmp-(a/b)*y;
25     return r;
26 }
27 int main()
28 {
29     int a,b,c;
30     scanf("%d%d%d",&a,&b,&c);
31     int y=gcd(a,b);
32     if(c%y!=0)
33     {
34         printf("No Answer");
35         return 0;
36     }
37     exgcd(a,b,x,y);
38     while(x<0)
39     {
40         x=x+b;
41     }
42     x=x*c;
43     printf("%d",x);
44     return 0;
45 }

 4.求排列数

  (1)基本排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n)/f(n-m));
15     return 0;
16 }

  (2)圆排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n)/(f(n-m)*m));
15     return 0;
16 }

  (3)全排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n));
15     return 0;
16 }

  (4)项链排列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n;
13     scanf("%d",&n);
14     if(n==1||n==2)
15     printf("1");
16     else
17     printf("%d",f(n-1)/2);
18     return 0;
19 }

5.求组合数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f(int n)
 6 {
 7     if(n==0)return 1;
 8     else return n*f(n-1);
 9 }
10 int main()
11 {
12     int n,m;
13     scanf("%d%d",&n,&m);
14     printf("%d",f(n)/(f(m)*(n-m)));
15     return 0;
16 }

6.快速幂

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio> 
 4 using namespace std;
 5 int fastpow(int a,int b)
 6 {
 7     int r=1;
 8     int base=a;
 9     while(b!=0)
10     {
11         if(b%2!=0)
12         r=r*base;
13         base=base*base;
14         b=b/2;
15     }
16     return r;
17 }
18 int main()
19 {
20     int a,b;
21     scanf("%d%d",&a,&b);
22     printf("%d",fastpow(a,b));
23     return 0;
24 }

7.斐波那契数列

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int main()
 6 {
 7     int n;
 8     scanf("%d",&n);
 9     double x=sqrt(5.0);
10     int ans=( pow ( ( ( 1+x ) / 2.0 ) , n ) / x - pow ( ( ( 1 - x ) / 2.0 ), n ) /x);
11     printf("%d",ans);
12     return 0;
13 }
 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[10001];
 6 int main()
 7 {
 8     int n;
 9     a[1]=1;
10     a[2]=1;
11     scanf("%d",&n);
12     for(int i=3;i<=n;i++)
13     {
14         a[i]=a[i-1]+a[i-2];
15     }
16     cout<<a[n];
17     return 0;
18 }
 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[10001];
 6 int f(int n)
 7 {
 8     if(n==1||n==2)return 1;
 9     else return f(n-1)+f(n-2);
10 }
11 int main()
12 {
13     int n;
14     a[1]=1;
15     a[2]=1;
16     scanf("%d",&n);
17     printf("%d",f(n));
18     return 0;
19 }

8.求二元一次不定方程

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int x,y;
 6 int gcd(int a,int b)
 7 {
 8     if(b==0)
 9     return a;
10     else 
11     return gcd(b,a%b);
12 }
13 int exgcd(int a,int b,int &x,int &y)
14 {
15     if(b==0)
16     {
17         x=1;
18         y=0;
19         return a;
20     }
21     int r=exgcd(b,a%b,x,y);
22     int tmp=x;
23     x=y;
24     y=tmp-(a/b)*y;
25     return r;
26 }
27 int main()
28 {
29     int a,b,c;
30     scanf("%d%d%d",&a,&b,&c);
31     int y=gcd(a,b);
32     if(c%y!=0)
33     {
34         printf("No Answer");
35         return 0;
36     }
37     exgcd(a,b,x,y);
38     while(x<0)
39     {
40         x=x+b;
41         y=y+b;
42     }
43     x=x*c;
44     printf("%d %d",x,y);
45     return 0;
46 }

9.欧拉定理

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<stack>
 5 using namespace std;
 6 stack<double>s;
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     int ll=n;
12     for(int i=2;i<=n-1;i++)
13     {
14         if(ll%i==0)
15         {
16             s.push(i);
17             while(ll%i==0)
18             ll=ll/i;
19         }
20     }
21     double ans=n;
22     while(s.size()!=0)
23     {
24         double p=s.top();
25         s.pop();
26         ans=ans*(double)(1.0-1.0/p);
27     }
28     printf("%.3lf",ans);
29     return 0;
30 }

 10.威尔逊定理判定素数

感觉把这个定理玩坏了。。因为它只能判断n<=35......。。。。比暴力都弱。。。。。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio> 
 4 #include<cmath>
 5 using namespace std;
 6 long long int f(int p)
 7 {
 8     if(p==0)
 9     return 1;
10     else return p*f(p-1);
11 }
12 int main()
13 {
14     int n;
15     scanf("%d",&n);
16     long long int ans=f(n-1);
17     if(ans%n==n-1)
18     printf("YES");
19     else 
20     printf("NO");
21     return 0;
22 }

11.Catalan数

 1 #include<iostream>
 2 using namespace std;
 3 long long int f[1001];
 4 int main()
 5 {
 6     int n;
 7     f[2]=1;
 8     f[3]=1;
 9     cin>>n;
10     n=n+2;
11     for(int i=4;i<=n;i++)
12     {
13         for(int j=2;j<=n-1;j++)
14         {
15             f[i]=f[j]*f[i-j+1]+f[i];
16         }
17     }
18     cout<<f[n];
19     return 0;
20 }

12.Stirling斯特林数

  (1)第一类(旧noi放苹果问题)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int t;
 7 int n;
 8 int m; 
 9 int tot=0;
10 int f(int a,int b)
11 {
12     if(a<=1||b<=1)
13     return 1;
14     if(a<b)
15     return f(a,a);
16     else 
17     return f(a,b-1)+f(a-b,b);
18  } 
19 int main()
20 {
21 
22     cin>>t;
23     for(int i=1;i<=t;i++)
24     {
25         cin>>m>>n;
26         cout<<f(m,n)<<endl;
27     } 
28     return 0; 
29 }

  (2)第二类

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int t;
 7 int n;
 8 int m; 
 9 int tot=0;
10 int f(int a,int b)
11 {
12     if(a<=1||b<=1)
13     return 1;
14     if(a<b)
15     return f(a,a);
16     else 
17     return f(a-1,b-1)+f(a-1,b)*b;
18  } 
19 int main()
20 {
21 
22     cin>>t;
23     for(int i=1;i<=t;i++)
24     {
25         cin>>m>>n;
26         cout<<f(m,n)<<endl;
27      } 
28     return 0; 
29 }

 13.判断素数的常用方法

  (1)暴力:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=10000001;
 6 int vis[MAXN];
 7 int bc[MAXN];
 8 int now=1;
 9 int pd(int n)
10 {
11     for(int i=2;i<=sqrt(n);i++)
12     {
13         if(n%i==0)
14         return 0;
15     }
16     return 1;
17 }
18 int main()
19 {
20     int m,n;
21     scanf("%d",&n);
22         if(pd(n)==1)
23         {
24             printf("YES");
25         }
26         else
27         {
28             printf("NO");
29         }
30     return 0;
31 }

  (2)线性筛法

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=100000001;
 6 int vis[MAXN];
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     for(int i=2;i<=sqrt(n);i++)
12     {
13         if(vis[i]==0)
14         {
15             for(int j=i*i;j<=n;j=j+i)
16             {
17                 vis[j]=1;
18             }
19         }
20     }
21     if(vis[n]==0)
22     {
23         printf("Yes");
24     }
25     else 
26     {
27         printf("No");
28     }
29     return 0;
30  } 

  (3)费马小定理(高能算法)

 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("%lld",&n);
64     cin>>n;
65     for(int i=1;i<=n;i++)
66     {
67         if(check(i))
68         {
69             printf("%d\n",i);
70         }
71     }
72     
73     return 0;
74 }

  (4)威尔逊定理判定素数(基本可以无视)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio> 
 4 #include<cmath>
 5 using namespace std;
 6 long long int f(int p)
 7 {
 8     if(p==0)
 9     return 1;
10     else return p*f(p-1);
11 }
12 int main()
13 {
14     int n;
15     scanf("%d",&n);
16     long long int ans=f(n-1);
17     if(ans%n==n-1)
18     printf("YES");
19     else 
20     printf("NO");
21     return 0;
22 }
23 
24 威尔逊定理(判定素数)

14.筛法求欧拉函数([SDOI2008]仪仗队)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=100001;
 7 int euler[MAXN];
 8 int ans=1;
 9 int main()
10 {
11     int n;
12     scanf("%d",&n);
13     n--;
14     euler[1]=1;
15     for(int i=2;i<=n;i++)
16         euler[i]=i;
17     for(int i=2;i<=n;i++)
18     {
19         if(euler[i]==i)
20             for(int j=i;j<=n;j+=i)
21                 euler[j]=euler[j]/i*(i-1);
22         ans+=euler[i];
23     }
24     printf("%d",ans*2+1);
25     return 0;
26 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

POJ A Knight's Journey

题意:给你一定的格子的棋盘,一匹马是否可以遍历完全整个棋盘 1 #include<stdio.h> 2 #include<string.h> 3 cons...

36010
来自专栏数据结构与算法

洛谷P4213 Sum(杜教筛)

题目描述 给定一个正整数N(N\le2^{31}-1)N(N≤231−1) 求ans_1=\sum_{i=1}^n\phi(i),ans_2=\sum_{i=1...

2956
来自专栏Java成长之路

google Guava之EventBus

EventBus是Guava的事件处理机制,是设计模式中的观察者模式(生产/消费者编程模型)的优雅实现,在应用中可以处理一些异步任务。对于事件监听和发布订阅模式...

2552
来自专栏数据结构与算法

BZOJ2462: [BeiJing2011]矩阵模板(二维hash)

二维矩阵hash,就是对行和列分配一个不同的base,然后分别做一遍hash,这样会减少冲突的概率。

811
来自专栏数据结构与算法

模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板

图论 最短路 SPFA 1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 using...

29311
来自专栏calmound

畅通工程再续(最小生成树)

这道题被坑的难受,很基础的题目,但是还是wa的郁闷,主要的错误是不懂的分析,导致变量的定义出错,记录k点的最短边要double的却依旧写int导致wa的找不出错...

3187
来自专栏数据结构与算法

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长...

781
来自专栏数据结构与算法

洛谷P1351 联合权值(树形dp)

872
来自专栏数据结构与算法

LOJ#2552. 「CTSC2018」假面(期望 背包)

转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

1594
来自专栏数据结构与算法

HUST 1017 - Exact cover

Time Limit: 15s Memory Limit: 128MB Special Judge Submissions: 7636 Solved: 38...

3327

扫码关注云+社区

领取腾讯云代金券