各种数论模板不断更新绝对精品-白红宇

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

阅读量：6543 次

发布时间：2019-06-24

本文共 12321 字，大约阅读时间需要 41 分钟。

1.筛法求素数

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           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
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int gcd(int x,int y) 7 { 8     if(y==0) 9     return x;10     else11     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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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     else17     printf("%d",f(n-1)/2);18     return 0;19 }

项链排列

5.求组合数

1 #include
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
           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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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<

递推

1 #include
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 stack
          
           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
      
        2 #include
       
         3 #include
        
           4 #include
         
           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
      
        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<

Catalan数

12.Stirling斯特林数

　　（1）第一类（旧noi放苹果问题）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           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
          
           >t;23     for(int i=1;i<=t;i++)24     {25         cin>>m>>n;26         cout<
           
            <

第一类斯特林数

　　（2）第二类

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           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
          
           >t;23     for(int i=1;i<=t;i++)24     {25         cin>>m>>n;26         cout<
           
            <

第二类斯特林数

13.判断素数的常用方法

　　（1）暴力：

1 #include
      
        2 #include
       
         3 #include
        
          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         else27         {28             printf("NO");29         }30     return 0;31 }

暴力求素数

　　（2）线性筛法

1 #include
      
        2 #include
       
         3 #include
        
          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
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            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
      
        2 #include
       
         3 #include
        
           4 #include
         
           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
      
        2 #include
       
         3 #include
        
          4 #include
         
           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 }