欧拉函数与中国剩余定理

中国剩余定理（大神博客）：https://www.cnblogs.com/MashiroSky/p/5918158.html

中国剩余定理（大神板子）：https://www.cnblogs.com/czsharecode/p/9736807.html

欧拉函数：欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。

欧拉函数的公式：φ(x)=x*(1-1/p1)*(1-1/p2).....其实很好理解。在1~x的范围内，去一个数是p1的倍数的概率为1/p1,是p2的倍数的概率是1/p2，不是p1的倍数的概率为1-1/p1,不是p2的倍数的概率为1-1/p2,

所以不是p1的倍数也不是p2的倍数的概率为(1-1/p1)*(1-1/p2)，其余质因子同理。所以φ(x)=x*(1-1/p1)*(1-1/p2).....。

可以用质因子分解的模板来求欧拉函数：

void solve(){
    ll m;
    cin>>m;
    ll c=sqrt(m);
    ll ans=m;
    for(ll i=2;i<=c;i++){
        if(m%i==0){
            ans=ans/i*(i-1);
            while(m%i==0){
                m/=i;
            }
        }

    }
    if(m!=1) ans=ans/m*(m-1);
    cout<<ans<<endl;
}

欧拉函数例题： X - Same GCDs CodeForces - 1295D

题目大意：在区间[0,m-1)内求满足gcd(a,m)=gcd(a+x,m)的个数，根据辗转相除，gcd(a+x,m)=gcd(m,(a+x)%m)=gcd(a,m)，令a+x=k，那么gcd(a,m)=gcd(k%m,m)。令i=k%m。那么gcd(a,m)=gcd(i,m)。

其中0<=i<=m-1。那么就是求gcd(i/q,m/q)=1的个数其中q=gcd(a,m)。也就是求m/q的欧拉函数.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    ll n,m;
    cin>>n>>m;
    ll c=__gcd(n,m);
    ll a=m/c;
    c=sqrt(a);
    ll ans=a;
    for(ll i=2;i<=c;i++){
        if(a%i==0){
            ans=ans/i*(i-1);
            while(a%i==0){
                a/=i;
            }
        }

    }
    if(a!=1) ans=ans/a*(a-1);
    cout<<ans<<endl;
}
int main()
{
    ll t;
    cin>>t;
    while(t--) solve();


    return 0;
}

中国剩余定理例题：http://poj.org/problem?id=1006 （POJ 1006）

关于中国剩余定理无非就是求几个方程

n1=mod1+x1*t1。。。n2=mod2+x2*t2。。。n3=mod3+x3*t3.等等。。。

n1的求法就是x2与x3的公倍数，然后关于x1求逆元，再乘以mod1，注意这里求逆元时要用exgcd求，不能用ksm，费马小定理要求互质。

中国剩余定理板子

void exgcd(ll a,ll b,ll& x,ll& y){
    if(!b){
        x=1;
        y=0;
    }
    else{
        exgcd(b,a%b,y,x);
        y-=x*(a/b);
    }
}
ll CRT(ll a[],ll m[],ll n)// 数组a是余数数组，数组m是基础数数组,n是数的个数
{
    ll M = 1;
    ll ans = 0;
    for(ll i=1; i<=n; i++)
        M *= m[i];
    for(ll i=1; i<=n; i++)
    {
        ll x, y;
        ll Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        // x为Mi关于m[i]的逆元。
        ans = (ans + Mi * x * a[i]) % M;
    }
    ans-=d;
    if(ans <=0) ans += M;
    return ans;
}

ACcode:

#include<iostream>
#include<cstdio>
using namespace std;
typedef  long long ll;
int d;
ll arr[10];
ll mod[10];
void exgcd(ll a,ll b,ll& x,ll& y){
    if(!b){x=1; y=0;}
    else{ exgcd(b,a%b,y,x); y-=x*(a/b); }
}
ll CRT(ll a[],ll m[],ll n)
{
    ll M = 1;
    ll ans = 0;
    for(ll i=1; i<=n; i++)
        M *= m[i];
    for(ll i=1; i<=n; i++)
    {
        ll x, y;
        ll Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        // x为Mi关于m[i]的逆元。
        ans = (ans + Mi * x * a[i]) % M;
    }
    ans-=d;
    if(ans <=0) ans += M;
    return ans;
}
int main()
{
    arr[1]=23;
    arr[2]=28;
    arr[3]=33;
    int t=1;
    while(cin>>mod[1]){
        for(ll i=2;i<=3;i++) cin>>mod[i];
        cin>>d;
        if(mod[1]==-1) break;
        printf("Case %d: the next triple peak occurs in %d days.
",t++,CRT(mod,arr,3));
    }
    return 0;
}

关于中国剩余定理还有一个是基础数不互质的情况。稍后补充。。。。