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

 

 

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

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

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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
         
          >=1;25         }26     return a<
         
        
       
      
     

 

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
     
       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     else15     {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\n");29     else 30     {31         x=x*(k/d);32         y=(k-a*x)/b;33         cout<
      
       <<" "<
       
        <
       
      
     

 

3：快速幂

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

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

 

4:快速乘

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

1 //快速乘相当于乘法，例 3 5 10 =3*5%10 2 #include
     
       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<
      
       <
      
     

 

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

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

　　使用快速幂

#include
     
      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('\n');        return;    }    for(;z;z/=10)r[++len]=z%10;    while(len)putchar(r[len--]+48);    putchar('\n');}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
     
      using namespace std;long long inv[3000010];long long n,p;int main(){    scanf("%lld%lld",&n,&p);    inv[1]=1;    printf("1\n");    for(int i=2;i<=n;i++)        inv[i]=(p-(p/i))*inv[p%i]%p,printf("%lld\n",inv[i]);//需牢记递推式    return 0;    }
     

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

　　实质求    ax+py=1    中的 x

 

1 #include
     
       2 #include
      
        3 #include
       
         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\n",x);32     }33     return 0;34 }
       
      
     

 

6.欧拉函数

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

　　摘自：

　欧拉函数详解　　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
     
       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<
      <<" "<
       
        <
       
     

 

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

 

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

　　很强大。。。

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