一.定理整理

1.欧拉定理(也称费马-欧拉定理):是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:

2.威尔逊定理:当且仅当p为素数时：①( p -1 )! ≡ -1 ( mod p )②(p-2)!≡1(mod p)

3.费马大定理:整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解

4.费马小定理:如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）

5.欧拉降幂:根据欧拉定理得:

6.孙子定理(中国剩余定理):

中国剩余定理给出了以下的一元线性同余方程组：

中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组有通解:

设

Mi=M/mi,t为(1/Mi)在mod mi 意义下的乘法逆元 Mi*ti=1(mod mi),则有如上通解

7.梅森素数：如果2^m次方-1为素数，那么m就是素数。如果m是素数，那么2^m-1就是第m个梅森素数

8.Fermat定理：如果n是素数，则a^(n-1)次方同余于1模n

9.Bezout定理. 如果a和b都是整数，则有整数x和y使得ax+by= GCD(a, b)。

推论：整数a和b互素当且仅当存在整数x和y使得ax+by=1。

10.积性函数：如果算术函数f对任意两个互素的正整数a和b，f(??)=?(?)?(?)，则f被称为积性函数（或乘性函数）；如果对任意两个正整数a和b，f(??)=?(?)?(?)，则f被称为完全积性函数（或完全乘性函数）。

如果p是一个素数，且k是正整数，则?(pk)=pk-pk-1。
如果m和n是互素的正整数，?(mn)=?(m)?(n)

11.梅森素数：如果一个数能够表示程若干个梅森素数的乘积，那么这个数的因子和可以表示为 2的幂，反之也成立

二.模板整理

1.素数打表模板线性筛法:


void set_prime()
{
    for(int i=1;i<maxn;i++)
        vis[i]=(i==1?false:true);//假设除了1以外都是素数
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=false;
            if(i%prime[j]==0) break;//保证被筛的是他最小的质因子
        }
    }
}

2.大数分解模板or求因子数模板:

ll div(ll x)//divide number x
{
    ll ans=1;
    for(int i=1;i<=cnt&&prime[i]*prime[i]<=x;i++)
    {
        bool flag=false;int c=0;
        while(x%prime[i]==0)
        {
            flag=true;
            x/=prime[i];
            cot[prime[i]]++;//统计因子数出现次数
            c++;
        }
        if(flag) ans*=c+1;
    }
    if(x>1)
    {
        cot[x]++;
        return ans*2;
    }
    return ans;
}

3.大数判素模板:

/***
前期需要开一个prime数组 {2,3,5,233,331}
and 快速幂函数与快速×函数
***/
bool Miller_Rabin(ll p) {
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    ll s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i) {
        if(p == prime[i]) return 1;
        ll t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1) {
            m = qmul(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}

4.欧拉函数打表模板:


void set_prime()
{
    for(int i=1;i<maxn;i++)
        vis[i]=(i==1?false:true);//假设除了1以外都是素数
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]) prime[++cnt]=i,oula[i]=i-1;
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=false;
            if(i%prime[j]==0)
            {
                oula[i*prime[j]]=oula[i]*prime[j];//当他们不互质时，有共同因子    
                break;
            }
            oula[i*prime[j]]=oula[i]*oula[prime[j]];//互质时积性函数分解
        }
    }
}

5.大数质因子分解与因子数(配合米勒罗宾)

inline ll qpow(ll a,ll b,ll c)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%c;
        b/=2;a=(a*a)%c;
    }
    return ans;
}
inline ll qmul(ll a,ll b,ll c)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%c;
        b/=2;a=(a+a)%c;
    }
    return ans;
}
bool Miller_Rabin(ll p) {
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    ll s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i) {
        if(p == prime[i]) return 1;
        ll t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1) {
            m = qmul(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}
ll div(ll x)//divide number x
{
    ll sum=0;
    for(int i=1;i<=cnt&&pprime[i]*pprime[i]*pprime[i]<=x;i++)
    {
        while(x%pprime[i]==0)
        {
            x/=pprime[i];
            sum++;
        }
    }
    if(x>1)
    {
        if(Miller_Rabin(x)) return sum+1;//如果剩余为质数
        else if((ll)sqrt(x)*(ll)sqrt(x)==x) return sum+2;//如果剩余为平方数
        else return sum+2;// 为两个质数
    }
    return sum;
}

6.素数区间筛&&偏移筛法

void inint()
{
    memset(vis,true,sizeof(vis));
    vis[1]=false;
    for(int i=2;i<50000;i++)
    {
        if(vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<50000;k+=i)
                vis[k]=false;
        }
    }
}
/**先外层打表 sqrt(最大值)的素数**/ 
if(n==1) other[0]=false;// 区间端点为1,1不是素数昂~
for(int i=1;i<=cnt;i++) {
       ll x=prime[i];
       for(ll k=max(2ll,(n+x-1)/x)*x;k<=m;k+=x)
           other[k-n]=false;
        }

7.卡特兰数?

inline LL catalan(LL N, LL MOD) { return comb(2*N, N, MOD)/(N+1); }

To be continue

数论定理整理与模板整理

一.定理整理

二.模板整理