zhangas

Pay more attention

0%

数学知识

Posted on Edited on

数论

质数判断(试除法)

复杂度为O(sqrt(n))
若n%d==0, 则n%n/d==0
只需d<=n/d 即d*d<=n

1
2
3
4
5
6
7
8
9
10
11
12
bool checkprime(int n){
    if(n<2){
        return false;
    }
    //不写成i*i<=n是怕int类型溢出
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

分解质因数(试除法)

复杂度为O(logn)~O(sqrt(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void divide(int n){
    if(n<2){
        return;
    }
    for(int i=2;i<=n/i;i++){
        if(n%i==0){//i是质因数
            int s=0;
            while(n/i==0){
                n/=i;
                s++;
            }
            cout<<i<<" "<<s<<endl;
        }
    }
    if(n>1){
        cout<<n<<" "<<1<<endl;
    }
    pust("");
    return;
}

筛质数 统计质数个数

① 埃式筛法
唯一分解定理 任意合数可由素数p1^a1 p2^a2 p3^a3…pk^a3之积表示
(算术基本定理: 任何一个大于1的合数 N可以唯一分解成有限个质数的乘积)
1/2+1/3+…+1/n之和称为调和级数 当n->∞时 Σ->ln n+c (c称为欧拉常数≈0.57721)
时间复杂度为O(nloglogn)

1
2
3
4
5
6
7
8
9
10
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[cnt++]=i;
            for(int j=i+i;j<=n;j+=i){
                st[j]=true;
            }
        }
    }
}

② 线性筛法
根据素数定理 从2到x的素数个数为x/ln x
若只遍历素数 时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cnt;//质数的数量 
int primes[N];//从2到n的质数集 
bool st[N];//判断是否为质数 
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			prime[cnt++]=i;
		}
        for(int j=0;primes[j]<n/i;j++){
            st[primes[j]*i]=true;//用最小质因子去筛合数
            if(i%primes[j]==0){
                break;
            }
        }
	}
}

试除法求一个数的所有约数

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> get_advisor(int n){
    vector<int> a;
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            a.push_back(i);
            if(i!=n/i){
                a.push_back(n/i);
            }
        }
    }
    sort(a.begin(),a.end());
    return a;
}

约数个数 约数之和

约数个数定理:任何大于1的正整数n可以表示分解质因数n=Π(pi^ai)
则n的正约数个数为Π(ai+1) (pi^ai的约数有pi^1 pi^2…pi^ai共有ai+1个)
INT范围内 最大的约数个数为1536个
n的约数之和为Π(pi^0+pi^1+…+pi^ai)可由乘法分配律展开证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//给定n个整数ai 求这些数的乘积的约数的个数
//利用哈希表存储pi的ai次方 约数的个数为Π(ai+1)
const int mod=1e9+7;//数据大需要取模
unordered_map<int,int>primes;
int main(){
    int n;cin>>n;
    while(n--){
        int x;cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1){//如果x很大的话 x的质因数为自身
            primes[x]++;
        }
    }
    LL res=1;//求约数的个数
    for(auto prime:primes){
        res=res*(prime.second+1)%mod;
    }
    cout<<res<<endl;

    LL sum=1;//求约数的和
    for(auto prime:primes){
        int p=prime.first,a=prime.second;
        LL t=1;
        while(a--){//做法巧妙 求p^0 到p^a次方的和的计算
            t=(t*p+1)%mod;
        }
        sum=(sum*t)%mod;
    }
    cout<<sum<<endl;

    return 0;
}

欧几里得算法(辗转相除法)

证明: gcd(a,b)==gcd(b,a%b)=d;
a=xd b=yd 即证gcd((xd)%(yd),yd)==d
x y互质 故gcd(x%y,y)==1 同乘d 证毕

1
2
3
4
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
    //当b==0时 gcd(a,0)为a
}

欧拉函数

1∼N 中与 N互质的数的个数被称为欧拉函数,记为 φ(N).
在算数基本定理中 N=Π(pi^αi)则
φ(N)=N*Π(1-1/pi)

1-1/pi=(pi-1)/pi
容质原理
① 去掉p1、p2、p3…pn的所有倍数(可能一个数被去除了两次)
② 加上所有pipj的倍数(任意两个)
② 减去所有pipjpk的倍数(任意三个)
···
···
N-N/p1-N/p2…-N/pk
+N/(pipj) i,j∈[1,n]&& i!=j
-N/(pipj*pk) i,j,k∈[1,n]&& i!=j&& i!=k&& j!=k
···
···
化简可得到欧拉函数的计算式 (由组合数公式可以确定各式的正负)
欧拉函数与质因子的次数无关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//当i%pj==0时候 pj的质因子在i中已经出现过 根据算数基本定理,所以pj*i表示的底数与i的底数相同

//求欧拉函数
typedef long long ll;
ll phi(ll a){
    ll res=a;
    for(int i=2;i<=a/i;i++){//求质数
        if(a%i==0){
            //与分解的底数有关 与幂指数无关
            res=res*(i-1)/i;
        }
        while(a%i==0){
            a/=i;
        }
    }
    if(a>1){
        res=res*(a-1)/a;
    }
    return a;
}
//筛法求欧拉函数
int primes[N],st[N],phi[N];//储存欧拉函数的值
int cnt;//质数的个数
void get_eulers(int n){
    phi[1]=1;

    for(int i=2;i<=n/i;i++){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
            //p是质数的话 phi为 i-1
        }
        //用质数筛选
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]==true;
            if(i%primes[j]==0){
                phi[primes[j]*i]=phi[i]*primes[j];
                break;
            }
            else{
                phi[primes[j]*i]=phi[i]*(primes[j]-1);
            }
        }
    }
}

//欧拉定理: a^φ(n)≡1 (mod n) 
//费马定理: 当n为质数的时候 a^p-1≡1 (mod p)

快速幂

给定 n组a,k,p 求a^k mod p的值

1
2
3
4
5
6
7
8
9
10
11
12
13
//时间复杂度为O(log k)
typedef long long ll;
ll qmi(ll a,ll k,ll p){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

求逆元 (需满足p为质数)
设x为b的乘法逆元
a*x≡a/b(mod p) a与p互质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef long long ll;
int qmi(ll a,ll k,ll p){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
}
int main(){
    int n;cin>>n;
    ll a,p;
    while(n--){
        cin>>a>>p;
        if(a%p){//只有当a与p互质时 才有解
            cout<<qmi(a,p-2,p)<<endl;
        }
        else{
            puts("impossible");
        }
    }
    return 0;
}

裴蜀定理(拓展欧几里得实现)

对于任意正整数a,b 一定∃非0整数x, y s.t. ax+by=gcd(a,b)
根据拓展欧几里得定理 对给定a,b 求出满足条件的一组x和y
gcd(a,b)=gcd(b,a%b)
当b==0时 gcd(a,0)==a 对ax+0y==a a=1 b=0时成立
当b!=0时 gcd(b,a%b,y,x)==d by+(a%b)x=d && a%b==a-a/ba -> ax+b(y-a/bx)=d 故x不变 y更新为y-a/bx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=gcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
int main(){
    int x;cin>>x;
    int a,b,x,y;
    while(n--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

找到ax0+by0=d时
x=x0+b/dk y=y0+b/dk k∈Z 即为满足条件的通解

线性同余方程求解

给定a,b,m求 求是否∃x s.t. ax ≡ b(mod m)
-> ax=ym+b 令y’=-y ->ax+ym=b ->解∃的条件为gcd(a,m)| b
a是gcd(a,m)的倍数 m是gcd(a,m)的倍数 所以拓展a,m后的和一定也是gcd(a,m)的倍数
只有当gcd(a,m)| b时 才有解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;return b;
    }
    int d=gcd(b,a%b);
    y-=a/b*x;
}
int main(){
    int n;cin>>n;
    int a,b,m,x,y;
    while(n--){
        cin>>a>>b>>b;
        int d=exgcd(a,m,x,y);//求ax+my=d 对应x y d的值 
        if(b%d){//不满足gcd(a,m) |b
            puts("impossible");
        }
        else{//求ax+my=b 等式两边同乘b/d %m在m范围内
            cout<<(ll)x*(b/d)%m<<endl;
        }
    }
}

中国剩余定理

对a1…an和m1…mn 求最小的非负整数x
s.t. ∀i∈[1,n] x≡mi (mod ai)
记M为Πmi Mi为M/mi Mi^-1表示Mi模mi的逆
∴x=Σ ai* Mi* Mi^-1
数据范围
1≤ai≤231−1
1≤n≤25 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    int n;cin>>n;
    ll a1,a2,m1,m2;
    cin>>a1>>m1;
    //n=1 时 求x≡m1(mod a1) x=k1*a1+m1 k1∈Z 
    bool has_answer=true;//标识是否有答案
    for(int i=0;i<n-1;i++){
        cin>>a2>>m2;
        ll k1,k2;
        ll d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d){
            has_answer=false;
            break;
        }
        //k1a-k2a2=d 同乘以(m2-m1)/d
        k1*=(m2-m1)/d;
        //k1= k1+k1*(a2/d) 把k1化为满足条件的最小整数
        ll t= a2/d;
        //k1%t ∈ (-t,t) 
        k1 = (k1%t+t)%t;
        
        //更新m1 和a1 ->存储的答案
        m1 = k1*a1+m1;
        a1=abs(a1*a2/d);//a1更新为a1与a2 的的最小公倍数 为正数
    }
    if(has_answer){
        //x≡m1(mod a1) -> x=k1*a1+m1 k1∈Z
        cout<<(m1%a1+a1)%a1<<endl;
    }
    else{
        puts("-1");
    }
}

x=k1a1+m1
=(k1+k(a2/d))a1+m1
=a1k1+m1+k[a1,a2] a1与a2的最小公倍数 a1a2/d
∴m1 = k1a1+m1; a1=abs(a1*a2/d);

高斯消元

解的判断

① 完美阶梯型 唯一解
② 0=bn (bn!=0)无解
③ 0=0有无穷解

步骤

枚举每一列的 c
① 从第r列中 找到绝对值最大的一行
② 将该行换到最上面
③ 将该行第一个数变成1
④ 将下面所有行的第c列消成0

1

组合计数

数学公式: C(b,a)=a!/(b!*(a-b)!);
证明: 0!=1;
(n+1)!=(n+1)*n! 当n==0时
n!=1 证得

I 递推的方式:

a,b∈[1,2000]
C(b,a)=C(b,a-1)+C(b-1,a-1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//时间复杂度O(N^2)
const int N=2010,mod=1e9+7;
void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<n;j++){
            if(!j){//从i中选0个 为1种情况
                a[i][j]=1;
            }
            else{
                a[i][j]=a[i-1][j]+a[i-1][j-1];
            }
        }
    }
}
init();
cout<<c[a][b]<<endl;//O(1)的时间查询

II 预处理出阶乘和阶乘的逆元:

a,b∈[1,1e5] n∈[1,1e5]
数学公式: C(b,a)=a!/(b!*(a-b)!);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//时间复杂度O(Nlog N)
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int fact[N],infact[N];
int qmi(ll a,ll k,ll p){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int main(){
    //0!=1;
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=(ll)fact[i-1]*i%mod;
        infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    int n;cin>>n;
    while(n--){
        ll a,b;cin>>a>>b;
        cout<<(ll)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
    }
}

lucas定理

给定 n 组询问,每组询问给定三个整数 a,b,p,其中 p 是质数,请你输出 C(b,a)mod p 的值。
a,b∈[1,1e18]
p∈[1，1e5]
a,b对p取模
C(b,a)=C(b%p,a%p)*C(b/p,a/p) (mod p)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int p;
int qmi(int a,int k){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int C(int a,int b){
    //定义法
    int res=1;
    for(int i=b,j=1;i>=1;i--,j++){
        res=(ll)res*j%p;
        res=(ll)res*qmi(i,p-2,p)%p;
    }
    return res;

}
int lucas(ll a,ll b){
    if(a<p&&b<p){
        return C(a,b);
    }
    else{
        return (ll)C(a%p,b%p)+lucas(a/p,b/p);
    }
}
int main(){
    int n;cin>>n;
    while(n--){
        ll a,b;cin>>a>>b;
        cout<<lucas(a,b)<<endl;
    }
}

高精度乘法 (不求模)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//线性筛
bool st[N];
int primes[N];
int cnt;
void get_primes(int n){
    for(int i=2;i<=n;i++){
        //如果i是质数
        if(!st[i]){
            primes[cnt++]=i;
        }
        //用i去筛选i的倍数
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0){
                break;
            }
        }
    }
}
//指数 
int sum[N];//存储primes[i]对应的指数
int get(int n,int p){
    int res=0;
    while(n){
        res+=rn/p;
        n/=p;
    }
    return res;
}
vector<int> mul(vector<int> a,int b){
    vector<int> c;
    int t;
    for(int i=0;i<a.size();i++){
        t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t){
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
int main(){
    int a,int b;
    cin>>a>>b;
    //默认a大 求a质数表示的底数
    get_primes(a);

    //从1到a的质数线性筛选出primes[i]的指数
    for(int i=0;i<cnt;i++){
        int p=primes[i];
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }

    vector<int>res;
    res.push_back(1);

    for(int i=0;i<cnt;i++){
        //sum里面是乘的次数
        for(int j=0;j<sum[i];j++){
            res=mul(res,primes[i]);
        }
    }
    //输出
    for(int i=res.size()-1;i>=0;i--){
        cout<<res[i];
    }

    return 0;
}

卡特兰数

给定 n 个 0 和 n 个, 它们将按照某种顺序排成长度为 2n 的序列, 求它们能排列成的所有序列中, 能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个.

输出的答案对 1e9+7 取模
1≤n≤10^5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//答案为 C(n,2*n)-C(n-1,2*n) -> C(n,2*n)/(n+1)
//求n+1 %mod的逆元 fact[2*n] infact[n]  
typedef long long ll;
const int mod=1e9+7,N=2e5+10;//fact[]的访问到2*n
int fact[N],infact[N];
//快速幂 求逆元
int qmi(int a,int k,int p){
    int res=1;//初始化为1 a^k %p
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int main(){
    int n;cin>>n;
    //初始化边界 0!=1 1/(0!)=1
    fact[0]=infact[0]=1;
    //预处理出N
    for(int i=1;i<N;i++){
        fact[i]=(ll)fact[i-1]*i%mod;
        infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    //输出
    cout<<(ll)fact[2*n]*infact[n]%mod*infact[n]%mod*qmi(n+1,mod-2,mod)%mod;
}

容斥原理

给定一个整数 n 和 m 个不同的质数 p1 p2 …pm
请你求出 1∼n 中能被 p1 p2 …pm 中的至少一个数整除的整数有多少个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
typedef long long ll;
const int N=20;
int p[N];//储存质数
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++)cin>>p[i];
    int ans=0;//储存答案
    for(int i=1;i<1<<m;i++){
        int t=1;//质数的乘积
        int cnt=0;//2进制中1的个数 即取出的集合个数
        for(int j=0;j<m;j++){//遍历质数
            if(i>>j&1){
                cnt++;
                if((ll)t*p[j]>n){
                    t=-1;//不能选出
                    break;
                }
                t*=p[j];
            }
        } 
        if(t!=-1){
            if(cnt%2){//奇数
                ans+=n/t;
            }
            else{
                ans-=n/t;
            }
        }
    }
    // n/t -> n是p的倍数 集合为1p 2p 3p...np
    // n不是p的倍数 1p 2p ...(n/p)p 
    cout<<ans<<endl;
    return 0;
}

简单博弈论

Mex运算

设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;

1
2
3
4
5
6
7
//实现
for(int i=0;;i++){
    if(!S.count(i)){
        f[x]=i;
        return f[x];
    }
}

SG函数

在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····
yk的SG函数值构成的集合在执行mex运算的结果,即:
SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x){
    if(f[x]!=-1) return f[x];
    //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
    unordered_set<int> S;
    //有序集合,在函数内部定义,下一次递归中的S不与本次相同
    for(int i=0;i<m;i++){
        int sum=s[i];
        if(x>=sum) S.insert(sg(x-sum));
        //先延伸到终点的sg值后,再从后往前排查出所有数的sg值
    }

    for(int i=0;;i++) if(!S.count(i)) 
    return f[x]=i;
}