[模板]数学整合

数学整合：为10天后的考试准备！

1.1:欧几里得算法（位运算）

　　　目前接触到的最快的求GCD的算法，而且不算太长，值得一记（虽然没有什么题目卡GCD吧。。。）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #define man 10000000
 6 #define sc(x) scanf("%d",&x)
 7 using namespace std;
 8 int n,x,y;
 9 inline int gcd(int a,int b)
10 {
11     if(!a||!b)
12         return a^b;
13     int i=0,j=0;
14     while(!(a&1))
15         a>>=1,i++;
16     while(!(b&1))
17         b>>=1,j++;
18     while(a!=b)
19     {
20         if(a<b)
21             a^=b,b^=a,a^=b;
22         a-=b;
23         while(!(a&1))
24             a>>=1;
25         }
26     return a<<min(i,j);
27     }
28 int main()
29 {
30     for(;;)
31     {
32         sc(x);sc(y);
33         cout<<gcd(x,y)<<endl;
34         }
35     return 0;
36     }

1.2:普通版

　　代码简洁，实用！

1 //只打出主要的部分:
2 
3 int gcd(int a,int b)
4 {   if(b==0) return a;
5      else return gcd(b,a%b);
6     }

2:扩展欧几里得算法

　　 重点知识！必须牢记！还要知道各个变量的含义！

　　扩展欧几里得算法实质求的是 ax+by=c=k*gcd(a,b)

　　所以我们求的是 ax+by=gcd(a,b)

　　求出之后判断 c%gcd(a,b)是否等于0

　　若不能被整除，则代表无解；

　　若ax+by=gcd(a,b)的解为(x’,y’)，则ax+by=c的解(x,y)=(c/gcd(a,b)*x’, c/gcd(a,b)*y’)

 1 #include<bits/stdc++.h>
 2 #define man 110000
 3 #define sc(x) scanf("%lld",&x)
 4 #define LL long long
 5 using namespace std;
 6 LL a,b,k,x,y;
 7 LL exgcd(LL a,LL b,LL &x,LL &y)
 8 {
 9     if(b==0)
10     {
11         x=1;y=0;
12         return a;
13         }
14     else
15     {
16         LL ret=exgcd(b,a%b,x,y);
17         LL t=x;
18         x=y;
19         y=t-(a/b)*y;
20         return ret;
21         }
22     }
23 int main()
24 {
25     sc(a);sc(b);sc(k);
26     LL d=exgcd(a,b,x,y);
27     if(k%d!=0)
28         printf("No
");
29     else 
30     {
31         x=x*(k/d);
32         y=(k-a*x)/b;
33         cout<<x<<" "<<y<<endl;
34         }
35     return 0;
36     }

3：快速幂

　　这个实在没什么好讲的了。。。

 1 #include<bits/stdc++.h>
 2 #define sc(x) scanf("%d",&x)
 3 using namespace std;
 4 int n,m;
 5 int p,ans=1;
 6 void bPow(int a,int b,int p)//Binary_Pow
 7 {    int base=a;
 8     while(b)
 9     {
10         if(b&1) ans=ans%p*base;
11         base=base*base%p;
12         b>>=1;
13         }
14     }
15 int main()
16 {
17     sc(n);sc(m);sc(p);
18     bPow(n,m,p);
19     cout<<ans<<endl;
20     return 0;
21     }

4:快速乘

　　也没什么讲的，就是把快速幂的乘号变成加号（效率不错）

 1 //快速乘相当于乘法，例 3 5 10 =3*5%10
 2 #include<bits/stdc++.h>
 3 #define sc(x) scanf("%d",&x)
 4 using namespace std;
 5 int n,m;
 6 int p,ans=0;
 7 void bAdd(int a,int b,int p)
 8 {    int base=a;
 9     while(b)
10     {
11         if(b&1) ans=(ans+base)%p;
12         base=(base+base)%p;
13         b>>=1;
14         }
15     }
16 int main()
17 {
18     sc(n);sc(m);sc(p);
19     bAdd(n,m,p);
20     cout<<ans<<endl;
21     return 0;
22     }

5.乘法逆元 a*n ≡ 1（mod p）

　　5.1当p为素数时，我们可以直接使用费马小定理操作：

　　使用快速幂

#include<bits/stdc++.h>
using namespace std;
inline long long bpow(long long a,long long b,long long mod)
{    long long base=a,ans=1;
    while(b)
    {    if(b&1) ans=(ans*base)%mod;
        base=(base*base)%mod;
        b>>=1;
        }
    return ans;
    } 
void write(long long z)//快输
{    char r[1001011];
    long long len=0;
    if(!z)
    {
        putchar(48);
        putchar('
');
        return;
    }
    for(;z;z/=10)r[++len]=z%10;
    while(len)putchar(r[len--]+48);
    putchar('
');
}
long long n,p;
int main()
{    scanf("%lld%lld",&n,&p);
    for(long long i=1;i<=n;i++)
    write(bpow(i,p-2,p));
    return 0;
    }

　　5.2使用线性递推式进行求解

　　可以参照洛谷 P3811

#include<bits/stdc++.h>
using namespace std;
long long inv[3000010];
long long n,p;
int main()
{    scanf("%lld%lld",&n,&p);
    inv[1]=1;
    printf("1
");
    for(int i=2;i<=n;i++)
        inv[i]=(p-(p/i))*inv[p%i]%p,printf("%lld
",inv[i]);//需牢记递推式
    return 0;
    }

　　5.3使用欧几里得算法进行求解

　　实质求 ax+py=1 中的 x

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int n,mod;
 6 inline int read()
 7 {
 8     char c=getchar();int  flag=1,x=0;
 9     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();    return x*flag;
11 }
12 int x,y;
13 int exgcd(int a,int b,int &x,int &y)
14 {
15     if(b==0)
16     {
17         x=1,y=0;
18         return a;
19     }
20     int r=exgcd(b,a%b,x,y);
21     int tmp=x;x=y;y=tmp-(a/b)*y;
22     return r;
23 }
24 int main()
25 {
26     n=read(),mod=read();
27     for(int i=1;i<=n;i++)
28     {
29         int g=exgcd(i,mod,x,y);
30         while(x<0)    x+=mod;
31         printf("%d
",x);
32     }
33     return 0;
34 }

6.欧拉函数

　　欧拉函数其实较好理解，但需要记住一些结论

　　摘自：http://blog.csdn.net/w144215160044/article/details/51158735

 　欧拉函数详解

　　1.对一个正整数N，欧拉函数是小于N且与N互质的数的个数.。

　　2.例如φ(24)=8，因为1, 5, 7, 11, 13, 17, 19, 23均和 24 互质。

　　3.φ(n) = n*(1-1/p1)*(1-1/p2)*......(1-1/pn)   其中(p1.....pn)为N的素因子


欧拉函数的基本性质：

    ① N是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）

    ② 除了N=2,φ(N)都是偶数.

    ③ 小于N且与N互质的所有数的和是φ(n)*n/2。//感觉很重要...但又感觉用不到

    ④ 欧拉函数是积性函数——若m,n互质，φ(m*n)=φ(m)*φ(n)。

    ⑤ 当N为奇数时，φ(2*N)=φ(N)

    ⑥ 若N是质数p的k次幂，φ(N)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟N互质。

    ⑦ 当N是质数时，φ(N) = N-1

代码：

 1 #include<bits/stdc++.h>
 2 #define man 110000
 3 #define sc(x) scanf("%d",&x)
 4 #define LL long long
 5 using namespace std;
 6 int n;
 7 int p[man];
 8 inline void ola()
 9 {
10     for(int i=1;i<=n;i++)
11         p[i]=i;
12     for(int i=2;i<=n;i++)
13     {
14         if(p[i]==i)
15         {
16             for(int j=i;j<=n;j+=i)
17                 p[j]=p[j]/i*(i-1);//或p[j]-=p[j]/i;
18             }
19         }
20     }
21 int main()
22 {
23     sc(n);
24     ola();
25     for(int i=1;i<=n;i++)
26         cout<<i<<" "<<p[i]<<endl;
27     return 0;
28     }

 1 inline int euler(int n)
 2 {    int ret=n;
 3     for(int i=2;i*i<=n;i++)
 4     {    if(n%i==0)
 5         {    ret-=ret/i;
 6             while(n%i==0)
 7                 n/=i;
 8             }
 9         }
10     if(n>1)
11          ret-=ret/n;
12     return ret;
13     }

　　7.线性筛素数

　　这也是考试的时候不能打错的函数。十分重要的函数。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #define man 10000000
 7 using namespace std;
 8 int n,isprime[man],prime[man],p=0;
 9 inline void calcprime()
10 {
11     for(int i=2;i<=n;i++)
12     {
13         if(isprime[i]==0)
14         {    
15             prime[++p]=i;
16         }
17         for(int j=1;i*prime[j]<=n;j++)
18         {    
19             isprime[i*prime[j]]=1;
20             if(i%prime[j]==0)
21                 break;
22         }
23     }    
24 }
25 int main()
26 {    
27     memset(isprime,0,sizeof(isprime));
28     memset(prime,0,sizeof(prime));
29     cin>>n;
30     calcprime();
31     for(int i=1;i<=p;i++)
32         cout<<prime[i]<<endl;
33     return 0; 
34  }

8.线性筛欧拉函数与素数

　　很强大。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=1e7+5;
 8 int n;
 9 bool vis[N];
10 int p[N],m=0;
11 ll s[N],ans,phi[N];
12 void sieve(){
13     phi[1]=1;
14     for(int i=2;i<=n;i++){
15         if(!vis[i]){
16             p[++m]=i;
17             phi[i]=i-1;
18         }
19         for(int j=1;j<=m&&i*p[j]<=n;j++){
20             vis[i*p[j]]=1;
21             if(i%p[j]==0){
22                 phi[i*p[j]]=phi[i]*p[j];
23                 break;
24             }
25             phi[i*p[j]]=phi[i]*(p[j]-1);
26         }
27     }
28     for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];
29 }
30 int main(){
31     scanf("%d",&n);
32     sieve();
33     for(int i=1;i<=m;i++) ans+=s[n/p[i]];
34     printf("%lld",ans*2-m);
35 }

9.同余方程组（中国剩余定理）

注意：下面是洛谷典型的中国剩余定理的题目（洛谷P1495 曹冲养猪）的代码

　　　但我是用同余方程组解的。

　　　代码中同余方程为：P≡b(mod m)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 inline ll read()
 5 {    ll x=0;bool f=0;char ch=getchar();
 6     while(!isdigit(ch)){    f=(ch==45);ch=getchar();}
 7     while(isdigit(ch)) {    x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
 8     return f?(~x+1):x;
 9     }
10 ll n,x,y;
11 ll b1,b2,m1,m2;
12 ll exgcd(ll a,ll b,ll &x,ll &y)
13 {    if(b==0)
14     {    x=1;y=0;return a;}
15     ll ret=exgcd(b,a%b,x,y);
16     ll t=x;x=y;y=t-(a/b)*y;
17     return ret;
18     }
19 int main()
20 {    n=read();
21     m1=read();b1=read();
22     for(int i=1;i<n;i++)
23     {    m2=read();b2=read();
24         ll A=m1,B=m2,k=b2-b1;
25         ll d=exgcd(A,B,x,y);
26         x=(((x*(k/d))%(B/d))+(B/d))%(B/d);//对x取最小正整数解
27         b1=m1*x+b1;//新的b1为原来的P
28         m1=m1/d*m2;//新的m1为LCU（m1,m2）
29         }
30     printf("%lld
",b1);//因为b1始终是上一个同余方程的P，自然for循环结束之后的b1为题目所要求的P了
31     return 0;
32     }