LCX的算法笔记Week-3

数学知识

给定一个正整数 n，请你求出 1∼n 中质数的个数

• 筛质数（埃氏筛）

#include <iostream>
using namespace std;
const int N=1e6+10;
int n,cnt,primes[N];
bool state[N];
void getprimes(int n)
{
    for (int i=2; i<=n; i++) {
        if (state[i]) {
            continue;
        }
        primes[cnt++]=i;
        for (int j=i+i; j<=n; j+=i) {
            state[j]=true;
        }
    }
}
int main()
{
    cin>>n;
    getprimes(n);
    cout<<cnt;
}

• 筛质数（线性筛）

#include <iostream>
using namespace std;
const int N=1e6+10;
int n,cnt,primes[N];
bool state[N];
void getprimes(int n)
{
    for (int i=2; i<=n; i++) {
        if (!state[i]) {
            primes[cnt++]=i;
        }
        for (int j=0; primes[j]<=n/i; j++) {
            state[primes[j]*i]=true;
            if (i%primes[j]==0) {
                break;
            }
        }
    }
}
int main()
{
    cin>>n;
    getprimes(n);
    cout<<cnt;
}

判断一个数是不是质数

bool isprime(int n)
{
    if (n==1) {
        return false;
    }
    for (int i=2; i<=n/i; i++) {
        if (n%i==0) {
            return false;
        }
    }
    return true;
}

分解质因数

void divide(int n)
{
    for (int i=2; i<=n/i; i++) {
        int cnt=0;
        while (n%i==0) {
            n/=i;
            cnt++;
        }
        if (cnt) {
            cout<<i<<' '<<cnt<<endl;
        }
    }
    if (n>1) {
        cout<<n<<' '<<1<<endl;
    }
    cout<<endl;
}

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

void func(int x)
{
    vector<int> t;
    for (int i=1; i<=sqrt(x); i++) {
        if (x%i==0) {
            t.push_back(i);
            if (x/i!=i) {
                t.push_back(x/i);
            }
        }
    }
    sort(t.begin(),t.end());
    for (int i=0; i<t.size(); i++) {
        cout<<t[i]<<' ';
    }
    cout<<endl;
}

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 1e9+7 取模。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
unordered_map<int, int> primes;
int n;
ll ans=1;
int main() {
    cin>>n;
    while (n--) {
        int a;
        cin>>a;
        for (int i=2; i<=a/i; i++) {
            int res=0;
            while (a%i==0) {
                a/=i;
                res++;
            }
            primes[i]+=res;
        }
        if (a>1) {
            primes[a]++;
        }
    }
    for(auto i:primes) ans=ans*(i.second+1)%mod;
    cout<<ans;
    return 0;
}

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10⁹+7 取模。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
unordered_map<int, int> primes;
int n;
ll ans=1;
int main() {
    cin>>n;
    while (n--) {
        int a;
        cin>>a;
        for (int i=2; i<=a/i; i++) {
            int res=0;
            while (a%i==0) {
                a/=i;
                res++;
            }
            primes[i]+=res;
        }
        if (a>1) {
            primes[a]++;
        }
    }
    ll ans=1;
    for(auto i:primes)
    {
        int base=i.first,p=i.second;
        ll res=1;
        while (p--) {
            res=(res*base+1)%mod;
        }
        ans=ans*res%mod;
    }
    cout<<ans;
    return 0;
}

最大公约数

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

欧拉函数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n;
int main() {
    cin>>n;
    while (n--) {
        int a;
        cin>>a;
        int ans=a;
        for (int i=2; i<=a/i; 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;
    }
    return 0;
}

筛法求欧拉函数

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=1e6+10;
ll n,ans;
ll euler[N],prime[N],cnt;
bool state[N];
void geteuler()
{
    euler[1]=1;
    for (int i=2; i<=n; i++) {
        if (!state[i]) {
            prime[cnt++]=i;
            euler[i]=i-1;
        }
        for (int j=0; prime[j]<=n/i; j++) {
            int t=prime[j]*i;
            state[t]=true;
            if (i%prime[j]==0) {
                euler[t]=euler[i]*prime[j];
                break;
            }
            euler[t]=euler[i]*(prime[j]-1);
        }
    }
}
int main() {
    cin>>n;
    geteuler();
    for (int i=1; i<=n; i++) {
        ans+=euler[i];
    }
    cout<<ans;
    return 0;
}

扩展欧几里得算法

给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int n;
int exgcd(int a,int b,int & x,int & y)
{
    if (!b) {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b, a%b, y, x);
    y=y-a/b*x;
    return d;
}
int main() {
    cin>>n;
    while (n--) {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a, b, x, y);
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}

利用扩展欧几里得算法求线性同余方程

给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi)，如果无解则输出 impossible

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int n;
int exgcd(int a,int b,int & x,int & y)
{
    if (!b) {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b, a%b, y, x);
    y=y-a/b*x;
    return d;
}
int main() {
    cin>>n;
    while (n--) {
        int a,x,y,m,b;
        cin>>a>>b>>m;
        int d=exgcd(a, m, x, y);
        if (b%d) {
            cout<<"impossible"<<endl;
        }
        else cout<<(ll)x*b/d%m<<endl;
    }
    return 0;
}

扩展中国剩余定理

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x

满足 ∀i∈[1,n],x≡mi(mod ai)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n;
ll mod(ll x,ll m)
{
    return ((x%m)+m)%m;
}
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,m1;
    cin>>a1>>m1;
    bool flag=true;
    for (int i=1; i<n; i++) {
        int a2,m2;
        cin>>a2>>m2;
        ll k1,k2;
        ll d=exgcd(a1, a2, k1, k2);
        if ((m1-m2)%d) {
            flag=false;
            break;
        }
        k1*=(m2-m1)/d;
        k1=mod(k1, a2/d);
        m1=k1*a1+m1;
        a1=a1*a2/d;
    }
    ll ans=mod(m1, abs(a1));
    if (flag) {
        cout<<ans;
    }
    else cout<<-1;
    return 0;
}

高斯消元解线性方程组

输入一个包含 n 个方程 n 个未知数的线性方程组。方程组中的系数为实数。求解这个方程组。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const double eps=1e-6;
int n;
double a[N][N];
int gauss()
{
    int r,c;
    for ( c=0,r=0; c<n; c++) {
        int t=r;
        //findmax
        for (int j=r; j<n; j++) {
        //少了个fabs就wa啦 我超
            if (fabs(a[j][c])>fabs(a[t][c])) {
                t=j;
            }
        }
        if (fabs(a[t][c])<eps) {
            continue;
        }
        //swap
        for (int j=c; j<n+1; j++) {
            swap(a[t][j],a[r][j]);
        }
        //首位非0变1
        for (int j=n; j>=c; j--) {
            a[r][j]/=a[r][c];
        }
        //下面的行当前列变0
        for (int j=r+1; j<n; j++) {
            if(fabs(a[j][c])>eps){
            for (int k=n; k>=c; k--) {
                a[j][k]-=a[j][c]*a[r][k];
            }}
        }
        r++;
    }
    if (r<n) {
        for (int j=r; j<n; j++) {
            if (fabs(a[j][n])>eps) {
                return 2;//no solution
            }
        }
        return 1;//infinite
    }
    for (int i=n-1; i>=0; i--) {
        for (int j=n-1; j>=i+1; j--) {
            a[i][n]-=a[i][j]*a[j][n];
        }
    }
    return 0;
}
int main() {
    cin>>n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n+1; j++) {
            cin>>a[i][j];
        }
    }
    int t=gauss();
    if (t==0) {
        for (int i=0; i<n; i++) {
            cout<<fixed<<setprecision(2)<<a[i][n]<<endl;
        }
    }
    else if (t==1)
    {
        cout<<"Infinite group solutions";
    }
    else cout<<"No solution";
    return 0;
}

当方程组为异或线形方程组时

yxc：

求组合数C(a,b)

1. 从定义出发，时间复杂度O(n²)

   void init()
   {
       for (int i = 0; i < N; i ++ )
           for (int j = 0; j <= i; j ++ )
               if (!j) c[i][j] = 1;
               else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
   }

2. 从用阶乘求组合数的定义出发，初始化阶乘，并且利用费马小定理和快速幂求逆元

   时间复杂度O(kn)，k为比较小的系数。

   ll fpow(ll base,ll p)
   {
       ll res=1;
       while (p) {
           if (p&1) {
               res=res*base%mod;
           }
           base=base*base%mod;
           p>>=1;
       }
       return res;
   }
   void init()
   {
       fac[0]=inv[0]=1;
       for (int i=1; i<N; i++) {
           fac[i]=fac[i-1]*i%mod;
           inv[i]=fpow((int)fac[i], mod-2);
       }
   }
   ll C(int a,int b)
   {
       return fac[a]*inv[b]%mod*inv[a-b]%mod;
   }

3. 对于a,b都爆大的情况，利用lucas定理来求

   

   ll lucas(ll a,ll b)
   {
       if (a<p&&b<p) {
           return C(a, b);
       }
       return C(a%p, b%p)*lucas(a/p, b/p)%p;
   }

4. 对于需要输出高精度结果的组合数

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long ll;
   const int N=1e5+10;
   int primes[N],cnt,sum[N];
   bool state[N];
   vector<int> multi(vector<int> & a,int b)
   {
       vector<int> c;
       int t=0;
       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;
   }
   void getprimes(int n)
   {
       for (int i=2; i<=n; i++) {
           if (!state[i]) {
               primes[cnt++]=i;
           }
           for (int j=0; primes[j]<=n/i; j++) {
               state[primes[j]*i]=true;
               if (i%primes[j]==0) {
                   break;
               }
           }
       }
   }
   int getnum(int n,int p)
   {
       int res=0;
       while (n) {
           res+=n/p;
           n/=p;
       }
       return res;
   }
   int main() {
       int a,b;
       cin>>a>>b;
       getprimes(a);
       for (int i=0; i<cnt; i++) {
           int p=primes[i];
           sum[i]=getnum(a,p)-getnum(b, p)-getnum(a-b, p);
       }
       vector<int> ans;
       ans.push_back(1);
       for (int i=0; i<cnt; i++) {
           for (int j=0; j<sum[i]; j++) {
               ans=multi(ans,primes[i]);
           }
       }
   //    for (int i=0; i<cnt; i++) {
   //        cout<<primes[i]<<' ';
   //    }
   //    cout<<endl;
   //    for (int i=0; i<cnt; i++) {
   //        cout<<sum[i]<<' ';
   //    }
   //    cout<<endl;
       for (int i=ans.size()-1; i>=0; i--) {
           cout<<ans[i];
       }
       return 0;
   }

卡特兰数

C(2n,n)-C(2n,n-1)=C(2n,n)/n+1

适用情况

• 括号匹配
• 出栈次序
• n个节点构成的二叉树，共有多少种情形
• 01序列-给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

int main() {
    int n;
    cin>>n;
    int a=2*n,b=n;
    ll res=1;
    for (int i=a; i>b; i--) {
        res=res*i%mod;
    }
    for (int i=1; i<=b; i++) {
        res=res*fpow(i, mod-2)%mod;
    }
    res=res*fpow(b+1, mod-2)%mod;
    cout<<res;
    return 0;
}

容斥原理

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

用位运算来枚举所有情况，奇加偶减

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int p[17];
int main() {
    int n,m;
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        cin>>p[i];
    }
    ll ans=0;
    for (int i=1; i<1<<m; i++) {
        int cnt=0;
        ll res=1;
        int t=1;
        for (int j=0; j<m ; j++) {
            if (i>>j&1) {
                res*=p[j];
                cnt++;
                if (res>n) {
                    t=-1;
                    break;
                }
            }
        }
        if (t!=-1) {
            if (cnt%2) {
                ans+=n/res;
            }
            else ans-=n/res;
        }
    }
    cout<<ans;
}

博弈论

1. NIM游戏

   给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

   问如果两人都采用最优策略，先手是否必胜。

   所有石子堆数量异或起来若为正，则一定有操作可以使之为0，最后输的状态就是0，因此只要开局时为正则必胜

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n;
int main() {
    cin>>n;
    int res=0;
    while (n--) {
        int x;
        cin>>x;
        res^=x;
    }
    if (res) {
        cout<<"Yes";
    }
    else cout<<"No";
    return 0;
}

2. 台阶-Nim游戏

   现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。

   两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

   已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

   问如果两人都采用最优策略，先手是否必胜。

   和第一题类似，只要奇数台阶上石子数量异或起来为正就行啦

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n;
int main() {
    cin>>n;
    int res=0;
    for (int i=1; i<=n; i++) {
        int x;
        cin>>x;
        if (i&1) {
            res^=x;
        }
    }
    if (res) {
        cout<<"Yes";
    }
    else cout<<"No";
    return 0;
}

3. 集合-Nim游戏（sg函数）

   给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

   现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

   问如果两人都采用最优策略，先手是否必胜

   

   令终点sg函数值为0，递归求每个状态的sg值

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long ll;
   const int N=1e4+10;
   int a[N],f[N],h[N];
   int k,n;
   int sg(int x)
   {
       if (f[x]>0) {
           return f[x];
       }
       unordered_set<int> s;
       for (int i=0; i<k; i++) {
           int t=a[i];
           if (x>=t) {
               s.insert(sg(x-t));
           }
       }
       for (int i=0; ; i++) {
           if (!s.count(i)) {
               return f[x]=i;
           }
       }
   }
   int main() {
       cin>>k;
       for (int i=0; i<k; i++) {
           cin>>a[i];
       }
       cin>>n;
       int res=0;
       for (int i=0; i<n; i++) {
           cin>>h[i];
           res^=sg(h[i]);
       }
       if (res) {
           cout<<"Yes";
       }
       else cout<<"No";
       return 0;
   }

4. 拆分-Nim游戏

   给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。

   问如果两人都采用最优策略，先手是否必胜。

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long ll;
   const int N=1e4+10;
   int f[N];
   int x,n;
   int sg(int x)
   {
       if (f[x]>=0) {
           return f[x];
       }
       unordered_set<int> s;
       for (int i=0; i<x; i++) {
           for (int j=0; j<=i; j++) {
               s.insert(sg(i)^sg(j));
           }
       }
       for (int i=0; ; i++) {
           if (!s.count(i)) {
               return f[x]=i;
           }
       }
   }
   int main() {
       memset(f, -1, sizeof f);
       int res=0;
       cin>>n;
       while (n--) {
           cin>>x;
           res^=sg(x);
       }
       if (res) {
           cout<<"Yes";
       }
       else cout<<"No";
       return 0;
   }