[数论专题]

一：素数

int prime[N],p[N],tot;
void init()
{
    for(int i=2;i<N;i++)    prime[i]=1;
    for(int i=2;i<N;i++)
    {
        if(prime[i]==1) p[++tot]=i;
        for(int j=1;j<=tot;j++)
        {
            prime[i*p[j]]=0;
            if(i%p[j]==0)   break;
        }
    }
}

二：快速幂

LL pow_mod(LL a, LL b, LL p){//a的b次方求余p
    LL ret = 1;
    while(b){
        if(b & 1) ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}

快速乘

LL mul(LL a, LL b, LL p){//快速乘，计算a*b%p
    LL ret = 0;
    while(b){
        if(b & 1) ret = (ret + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ret;
}

三：gcd和lcm

lcm=a/gcd*b;

LL gcd(LL a, LL b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

LL gcd(LL a, LL b){
    return b ? gcd(b, a%b) : a;
}
//两种都可以

gcd(ka, kb) = k * gcd(a, b)

lcm(ka, kb) = k * lcm(a, b)

lcm(S/a, S/b) = S/gcd(a, b)

四：扩展欧几里得算法

已知 a，b 求 一组解 x，y 满足 ax+by = gcd(a, b) 这个公式

 void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b)
        {d = a; x = 1; y = 0;}
     else
    {
        ex_gcd(b, a%b, d, y, x); 
        y -= x*(a/b);
    }    
}

五：数论四大定理

1.威尔逊定理：

　　当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )

　　或者这么写( p -1 )! ≡ p-1 ( mod p )

　　或者说

　　若p为质数，则p能被(p-1)!+1整除

2.欧拉定理：

 

　　若n,a为正整数，且n,a互质，即gcd(a,n) = 1，则

　　　a^φ(n) ≡ 1 (mod n)

 

　　　φ(n) 是欧拉函数

 

  　　欧拉函数是求 1到n-1 中 与n互质的数 的数目

 3.中国剩余定理

　　假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组 (S)有解

#include<cstdio>
typedef long long LL;
const int N = 100000 + 5;
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
    if (!b) {d = a, x = 1, y = 0;}
    else{
        ex_gcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}
LL inv(LL t, LL p){//如果不存在，返回-1
    LL d, x, y;
    ex_gcd(t, p, x, y, d);
    return d == 1 ? (x % p + p) % p : -1;
}
LL china(int n, LL *a, LL *m){//中国剩余定理
    LL M = 1, ret = 0;
    for(int i = 0; i < n; i ++) M *= m[i];
    for(int i = 0; i < n; i ++){
        LL w = M / m[i];
        ret = (ret + w * inv(w, m[i]) * a[i]) % M;
    }
    return (ret + M) % M;
}
int main(){
    LL p[3], r[3], d, ans, MOD = 21252;
    int cas = 0;
    p[0] = 23; p[1] = 28; p[2] = 33;
    while(~scanf("%I64d%I64d%I64d%I64d", &r[0], &r[1], &r[2], &d) && (~r[0] || ~r[1] || ~r[2] || ~d)){
        ans = ((china(3, r, p) - d) % MOD + MOD) % MOD;
        printf("Case %d: the next triple peak occurs in %I64d days.
", ++cas, ans ? ans : 21252);
    }

}

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
PLL linear(LL A[], LL B[], LL M[], int n) {//求解A[i]x = B[i] (mod M[i]),总共n个线性方程组
    LL x = 0, m = 1;
    for(int i = 0; i < n; i ++) {
        LL a = A[i] * m, b = B[i] - A[i]*x, d = gcd(M[i], a);
        if(b % d != 0)  return PLL(0, -1);//答案不存在，返回-1
        LL t = b/d * inv(a/d, M[i]/d)%(M[i]/d);
        x = x + m*t;
        m *= M[i]/d;
    }
    x = (x % m + m ) % m;
    return PLL(x, m);//返回的x就是答案，m是最后的lcm值
}

4.费马小定理：

　　假如p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），若p能整除a，则a^(p-1) ≡0（mod p）。

　　或者说，若p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。

 

六：逆元

求单个逆元: 　　inv[a]=pow(a,mod-2,mod);

求n个数的逆元： inv[0]=inv[1]=1;　　inv[i]=(mod-mod/i)*inv[mod%i];

七：欧拉函数

#include<cstdio>
using namespace std;
const int N = 1e6+10 ;
int phi[N], prime[N];
int tot;//tot计数，表示prime[N]中有多少质数
void Euler(){
    phi[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!phi[i]){
            phi[i] = i-1;
            prime[tot ++] = i;
        }
        for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
            if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
            else{
                phi[i * prime[j] ] = phi[i] * prime[j];
                break;
            }
        }
    }
}

int main(){
    Euler();
}

八：卢卡斯定理

求Cnm,用逆元为O(n)的。

但若 n m 特别大，p很小的时候。

C(n, m) % p  =  C(n / p, m / p) * C(n%p, m%p) % p

 

九：康托展开

康托的一套算法可以正好产生n!个数字

比如：

123  ->  0

132  ->  1

213  ->  2

231  ->  3

312  ->  4

321  ->  5

void cantor(int s[], LL num, int k){//康托展开，把一个数字num展开成一个数组s，k是数组长度
    int t;
    bool h[k];//0到k-1，表示是否出现过
    memset(h, 0, sizeof(h));
    for(int i = 0; i < k; i ++){
        t = num / fac[k-i-1];
        num = num % fac[k-i-1];
        for(int j = 0, pos = 0; ; j ++, pos ++){
            if(h[pos]) j --;
            if(j == t){
                h[pos] = true;
                s[i] = pos + 1;
                break;
            }
        }
    }
}
void inv_cantor(int s[], LL &num, int k){//康托逆展开，把一个数组s换算成一个数字num
    int cnt;
    num = 0;
    for(int i = 0; i < k; i ++){
        cnt = 0;
        for(int j = i + 1; j < k; j ++){
            if(s[i] > s[j]) cnt ++;//判断几个数小于它
        }
        num += fac[k-i-1] * cnt;
    }
}

hdu 1430（坑）

十：抽屉原理