数论Day4

目录

质数

约数

欧拉函数

快速幂

扩展欧几里得算法

中国剩余定理

高斯消元

求组合数

容斥原理

博弈论

质数

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

输入格式

共一行，包含整数 nn。

输出格式

共一行，包含一个整数，表示 1∼n1∼n 中质数的个数。

数据范围

1≤n≤1061≤n≤106

输入样例：

8

输出样例：

4

#include 
#include 

using namespace std;

const int N = 1000010;

//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //标记;primes[j]一定是primes[j]*i的最小质因子
            st[primes[j]*i] = true;
            //表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
            //这样能保证每个数遍历一遍,而没有重复
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

约数

给定 nn 个正整数 aiai，对于每个整数 aiai，请你按照从小到大的顺序输出它的所有约数。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数 aiai。

输出格式

输出共 nn 行，其中第 ii 行输出第 ii 个整数 aiai 的所有约数。

数据范围

1≤n≤1001≤n≤100,
2≤ai≤2×1092≤ai≤2×109

输入样例：

2
6
8

输出样例：

1 2 3 6 
1 2 4 8 

#include 
#include 
#include 

using namespace std;

int n;

void get_divisors(int n)
{
    vector res;

    for (int i = 1; i <= n / i; i++) {
        if (n % i == 0) {
            res.push_back(i);

            if (i != n / i) {  // 避免 i==n/i, 重复放入 （n是完全平方数
                res.push_back(n / i);
            }
        }
    }

    sort(res.begin(), res.end());
    for (auto item : res) {
        cout << item << " ";
    }
    puts("");
}

int main()
{
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        get_divisors(x);
    }
    return 0;
}

给定 nn 个正整数 aiai，请你输出这些数的乘积的约数个数，答案对 109+7109+7 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数 aiai。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7109+7 取模。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

输入样例：

3
2
6
8

输出样例：

12

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

 

给定 nn 个正整数 aiai，请你输出这些数的乘积的约数之和，答案对 109+7109+7 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数 aiai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7109+7 取模。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

输入样例：

3
2
6
8

输出样例：

252

 

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map primes;

    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) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

 

给定 nn 对正整数 ai,biai,bi，请你求出每对数的最大公约数。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数对 ai,biai,bi。

输出格式

输出共 nn 行，每行输出一个整数对的最大公约数。

数据范围

1≤n≤1051≤n≤105,
1≤ai,bi≤2×1091≤ai,bi≤2×109

输入样例：

2
3 6
4 6

输出样例：

3
2

#include
using namespace std;

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

int main(){
    int n,a,b;
    cin>>n;
    while(n--) cin>>a>>b,cout< 
 
 
欧拉函数 
给定 nn 个正整数 aiai，请你求出每个数的欧拉函数。
 
欧拉函数的定义
 
 
 
1∼N1∼N 中与 NN 互质的数的个数被称为欧拉函数，记为 ϕ(N)ϕ(N)。
 若在算数基本定理中，N=pa11pa22…pammN=p1a1p2a2…pmam，则：
 ϕ(N)ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pmN×p1−1p1×p2−1p2×…×pm−1pm
 
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个正整数 aiai。
 
输出格式
 
输出共 nn 行，每行输出一个正整数 aiai 的欧拉函数。
 
数据范围
 
1≤n≤1001≤n≤100,
 1≤ai≤2×1091≤ai≤2×109
 
输入样例：
 
3
3
6
8
 
输出样例：
 
2
2
4
 
#include
using namespace std;
typedef long long ll;
int main()
{
    ll k;cin>>k;
    while(k--)
    {
        ll x;
        cin>>x;
        ll res=x;
        for(ll i=2;i<=x/i;i++)
            if(x%i==0)
            {
                while(x%i==0)x/=i;
                res=res/i*(i-1);   //注意先除再乘  N/pk*(pk-1); 
            }
        if(x>1)res=res/x*(x-1);
        cout< 
给定一个正整数 nn，求 1∼n1∼n 中每个数的欧拉函数之和。
 
输入格式
 
共一行，包含一个整数 nn。
 
输出格式
 
共一行，包含一个整数，表示 1∼n1∼n 中每个数的欧拉函数之和。
 
数据范围
 
1≤n≤1061≤n≤106
 
输入样例：
 
6
 
输出样例：
 
12
 

#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1000010;

int primes[N], cnt;
int phi[N];
bool st[N];

void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            phi[i] = 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;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_eulers(n);

    LL res = 0;
    for (int i = 1; i <= n; i++) res += phi[i];
    printf("%lldn", res);

    return 0;
}

作者：番茄酱
链接：https://www.acwing.com/solution/content/3952/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
快速幂 
给定 nn 组 ai,bi,piai,bi,pi，对于每组数据，求出 abiimodpiaibimodpi 的值。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含三个整数 ai,bi,piai,bi,pi。
 
输出格式
 
对于每组数据，输出一个结果，表示 abiimodpiaibimodpi 的值。
 
每个结果占一行。
 
数据范围
 
1≤n≤1000001≤n≤100000,
 1≤ai,bi,pi≤2×1091≤ai,bi,pi≤2×109
 
输入样例：
 
2
3 2 5
4 3 9
 
输出样例：
 
4
1
 
#include 

using namespace std;

typedef long long LL;

int quick_pow(int a, int k, int p)
{
    int res = 1 % p;
    while (k) {
        if (k & 1) {
            res = (LL)res * a % p;
        }
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int n;

int main()
{
    cin >> n;
    while (n--) {
        int a, k, p;
        cin >> a >> k >> p;
        cout << quick_pow(a, k, p) << endl;
    }
    return 0;
}

作者：Bug-Free
链接：https://www.acwing.com/solution/content/43588/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
给定 nn 组 ai,piai,pi，其中 pipi 是质数，求 aiai 模 pipi 的乘法逆元，若逆元不存在则输出 impossible。
 
注意：请返回在 0∼p−10∼p−1 之间的逆元。
 
乘法逆元的定义
 
 
 
若整数 b，mb，m 互质，并且对于任意的整数 aa，如果满足 b|ab|a，则存在一个整数 xx，使得 a/b≡a×x(modm)a/b≡a×x(modm)，则称 xx 为 bb 的模 mm 乘法逆元，记为 b−1(modm)b−1(modm)。
 bb 存在乘法逆元的充要条件是 bb 与模数 mm 互质。当模数 mm 为质数时，bm−2bm−2 即为 bb 的乘法逆元。
 
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个数组 ai,piai,pi，数据保证 pipi 是质数。
 
输出格式
 
输出共 nn 行，每组数据输出一个结果，每个结果占一行。
 
若 aiai 模 pipi 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
 
数据范围
 
1≤n≤1051≤n≤105,
 1≤ai,pi≤2∗1091≤ai,pi≤2∗109
 
输入样例：
 
3
4 3
8 5
6 3
 
输出样例：
 
1
2
impossible
 
#include 
using namespace std;
typedef long long LL;

LL qmi(int a, int b, int p)
{
    LL res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int n; cin >> n;
    while(n --){
        int a, p;
        cin >> a >> p;
        if(a % p == 0) puts("impossible");
        else cout << qmi(a, p - 2, p) << endl;
    }
    return 0;
}

作者：Hz
链接：https://www.acwing.com/solution/content/3054/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
扩展欧几里得算法 
给定 nn 对正整数 ai,biai,bi，对于每对数，求出一组 xi,yixi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)ai×xi+bi×yi=gcd(ai,bi)。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含两个整数 ai,biai,bi。
 
输出格式
 
输出共 nn 行，对于每组 ai,biai,bi，求出一组满足条件的 xi,yixi,yi，每组结果占一行。
 
本题答案不唯一，输出任意满足条件的 xi,yixi,yi 均可。
 
数据范围
 
1≤n≤1051≤n≤105,
 1≤ai,bi≤2×1091≤ai,bi≤2×109
 
输入样例：
 
2
4 6
8 18
 
输出样例：
 
-1 1
-2 1
 
#include
using namespace std;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 
}
int main(){
    int n,a,b,x,y;
    cin>>n;
    while(n--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout< 
给定 nn 组数据 ai,bi,miai,bi,mi，对于每组数求出一个 xixi，使其满足 ai×xi≡bi(modmi)ai×xi≡bi(modmi)，如果无解则输出 impossible。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一组数据 ai,bi,miai,bi,mi。
 
输出格式
 
输出共 nn 行，每组数据输出一个整数表示一个满足条件的 xixi，如果无解则输出 impossible。
 
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
 
输出答案必须在 intint 范围之内。
 
数据范围
 
1≤n≤1051≤n≤105,
 1≤ai,bi,mi≤2×1091≤ai,bi,mi≤2×109
 
输入样例：
 
2
2 3 6
4 3 5
 
输出样例：
 
impossible
-3
 
#include
using namespace std;
int n, x, y;
using LL = long long ;
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - a / b * y;
    return d;
}

int main()
{
    cin >> n;
    while (n --)
    {
        int a, b, m;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else 
        {
            x = (LL)x * b / d % m;
            cout << x << endl;
        }
    }
    return 0;
}

作者：sjytker
链接：https://www.acwing.com/solution/content/5937/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
中国剩余定理 
给定 2n2n 个整数 a1,a2,…,ana1,a2,…,an 和 m1,m2,…,mnm1,m2,…,mn，求一个最小的非负整数 xx，满足 ∀i∈[1,n],x≡mi(mod ai)∀i∈[1,n],x≡mi(mod ai)。
 
输入格式
 
第 11 行包含整数 nn。
 
第 2…n+12…n+1 行：每 i+1i+1 行包含两个整数 aiai 和 mimi，数之间用空格隔开。
 
输出格式
 
输出最小非负整数 xx，如果 xx 不存在，则输出 −1−1。
 如果存在 xx，则数据保证 xx 一定在 6464 位整数范围内。
 
数据范围
 
1≤ai≤231−11≤ai≤231−1,
 0≤mi 1≤n≤251≤n≤25
 
输入样例：
 
2
8 7
11 9
 
输出样例：
 
31
 
#include 
#include 
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
LL inline mod(LL a, LL b){
    return ((a % b) + b) % b;
}
int main(){
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for(int i = 1; i < n; i++){
        LL a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        LL d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d){ puts("-1"); return 0; }
        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    printf("%lldn", m1);
    return 0;
}

作者：墨染空
链接：https://www.acwing.com/solution/content/3539/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
 
高斯消元 
输入一个包含 nn 个方程 nn 个未知数的线性方程组。
 
方程组中的系数为实数。
 
求解这个方程组。
 
下图为一个包含 mm 个方程 nn 个未知数的线性方程组示例：
 
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含 n+1n+1 个实数，表示一个方程的 nn 个系数以及等号右侧的常数。
 
输出格式
 
如果给定线性方程组存在唯一解，则输出共 nn 行，其中第 ii 行输出第 ii 个未知数的解，结果保留两位小数。
 
如果给定线性方程组存在无数解，则输出 Infinite group solutions。
 
如果给定线性方程组无解，则输出 No solution。
 
数据范围
 
1≤n≤1001≤n≤100,
 所有输入系数以及常数均保留两位小数，绝对值均不超过 100100。
 
输入样例：
 
3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00
 
输出样例：
 
1.00
-2.00
3.00
 

#include
#include
using namespace std;

const int N = 110;
const double zero = 1e-6;
double a[N][N];
int n;
int gauss()
{
    //处理矩阵
    //枚举列
    int r=0;
    for(int j=0;ja[t][j]) t=k;//如果当前列的第k行元素大于设定的当前列第t行的元素,更新最大索引

        for(int k = j;k<=n;k++)
            swap(a[t][k],a[r][k]);

        //将当前列元素最大所在行的元素变为1 因为除数不能为0,若除数为0,说明当前列,已经满足上三角形类型
        if(fabs(a[r][j])=j;k--)   a[r][k]/=a[r][j];

        //将当前列除第r行外,其他行的元素变为0
        for(int k=r+1;k=j;l--)
                a[k][l]-=a[k][j]*a[r][l];
        r++;
    }
    //无解和无穷组解
    if(rzero)
                return 0;
        //如果不是无解,那么就是无穷多组解
        return 2;
    }
    //存在唯一解,逆序回去
    for(int i=n-1;i>=0;i--)
        for(int j = i+1;j<=n;j++){
            a[i][n]-=a[j][n]*a[i][j];
        }
    return 1;
}
int main()
{
    cin>>n;
    //读入矩阵
    for(int i=0;i>a[i][j];
    cout.setf(ios_base::fixed);
    cout.precision(2);
    int flag = gauss();
    if(!flag) cout<<"No solution";
    else if(flag%2) for(int i=0;i 
 
 
输入一个包含 nn 个方程 nn 个未知数的异或线性方程组。
 
方程组中的系数和常数为 00 或 11，每个未知数的取值也为 00 或 11。
 
求解这个方程组。
 
异或线性方程组示例如下：
 
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
 
其中 ^ 表示异或(XORXOR)，M[i][j]M[i][j] 表示第 ii 个式子中 x[j]x[j] 的系数，B[i]B[i] 是第 ii 个方程右端的常数，取值均为 00 或 11。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含 n+1n+1 个整数 00 或 11，表示一个方程的 nn 个系数以及等号右侧的常数。
 
输出格式
 
如果给定线性方程组存在唯一解，则输出共 nn 行，其中第 ii 行输出第 ii 个未知数的解。
 
如果给定线性方程组存在多组解，则输出 Multiple sets of solutions。
 
如果给定线性方程组无解，则输出 No solution。
 
数据范围
 
1≤n≤1001≤n≤100
 
输入样例：
 
3
1 1 0 1
0 1 1 0
1 0 0 1
 
输出样例：
 
1
0
0
 

#include 
#include 

using namespace std;

const int N = 110;

int n;
int a[N][N];
int gauss()
{
    int c,r;
    for(c=0,r=0;c=c;j--)//漏了
                    a[i][j] ^= a[r][j];
        r++;
    }
    // 判断
    if(r=0;i--)
        for(int j=i+1;j> n;
    for(int i=0;i> a[i][j];
    int t = gauss();
    if(t==0)
    {
        for(int i=0;i 
求组合数 
给定 nn 组询问，每组询问给定两个整数 a，ba，b，请你输出 Cbamod(109+7)Cabmod(109+7) 的值。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一组 aa 和 bb。
 
输出格式
 
共 nn 行，每行输出一个询问的解。
 
数据范围
 
1≤n≤100001≤n≤10000,
 1≤b≤a≤20001≤b≤a≤2000
 
输入样例：
 
3
3 1
5 3
2 2
 
输出样例：
 
3
10
1
 
#include
using namespace std;
const int mod = 1e9+7;
long long f[2010][2010];
int main()
{
    //预处理
    for(int i=0;i<=2000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) f[i][j]=1;
            else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
        }
    }
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        printf("%ldn",f[a][b]);
    }
}

作者：码
链接：https://www.acwing.com/solution/content/21902/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
给定 nn 组询问，每组询问给定两个整数 a，ba，b，请你输出 Cbamod(109+7)Cabmod(109+7) 的值。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一组 aa 和 bb。
 
输出格式
 
共 nn 行，每行输出一个询问的解。
 
数据范围
 
1≤n≤100001≤n≤10000,
 1≤b≤a≤1051≤b≤a≤105
 
输入样例：
 
3
3 1
5 3
2 2
 
输出样例：
 
3
10
1
 

#include
using namespace std;
const int mod=1e9+7,N=1e5+10;
typedef long long LL;
long long fac[N],infac[N];
int quick_pow(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main()
{
    int n;
    fac[0]=infac[0]=1;
    for(int i=1;i<=1e5;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        infac[i]=(LL)infac[i - 1] * quick_pow(i,mod-2,mod)%mod;
    }
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<(LL)fac[a] * infac[b] % mod * infac[a - b] % mod< 
给定 nn 组询问，每组询问给定三个整数 a,b,pa,b,p，其中 pp 是质数，请你输出 CbamodpCabmodp 的值。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一组 a,b,pa,b,p。
 
输出格式
 
共 nn 行，每行输出一个询问的解。
 
数据范围
 
1≤n≤201≤n≤20,
 1≤b≤a≤10181≤b≤a≤1018,
 1≤p≤1051≤p≤105,
 
输入样例：
 
3
5 3 7
3 1 5
6 4 13
 
输出样例：
 
3
3
2
 

#include 
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 6;

ll poww(ll a, ll b, ll p){
    ll res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll C(ll a, ll b, ll p){
    ll res = 1;
    for(int i = 1, j = a;i <= b;++i, --j){
        res = res * j % p;
        res = res * poww(i, p - 2, p) % p;
    }
    return res % p;
}

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

int main(){
    int n; sd(n);
    while(--n >= 0){
        ll a, b; sld(a), sld(b);
        ll p; sld(p);
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

作者：嘤嘤嘤0
链接：https://www.acwing.com/solution/content/5244/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
输入 a,ba,b，求 CbaCab 的值。
 
注意结果可能很大，需要使用高精度计算。
 
输入格式
 
共一行，包含两个整数 aa 和 bb。
 
输出格式
 
共一行，输出 CbaCab 的值。
 
数据范围
 
1≤b≤a≤50001≤b≤a≤5000
 
输入样例：
 
5 3
 
输出样例：
 
10
 
#include
using namespace std;

const int N=5010;
int primes[N],cnt;
bool st[N];
int sum[N];

vector mul(vector a,int b){
    vector c;
    int t=0;

    for(int i=0;i>a>>b;

    get_primes(a);

    for(int i=0;i res;
    res.push_back(1);

    for(int i=0;i=0;i--) cout< 
给定 nn 个 00 和 nn 个 11，它们将按照某种顺序排成长度为 2n2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 00 的个数都不少于 11 的个数的序列有多少个。
 
输出的答案对 109+7109+7 取模。
 
输入格式
 
共一行，包含整数 nn。
 
输出格式
 
共一行，包含一个整数，表示答案。
 
数据范围
 
1≤n≤1051≤n≤105
 
输入样例：
 
3
 
输出样例：
 
5
 
#include 

using namespace std;

typedef long long LL;

const int N = 200010, mod = 1e9 + 7;

int n;
int fact[N], infact[N];

int ksm(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

void init() {
    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] * ksm(i, mod - 2) % mod;
    }
}

int main() {
    init();
    cin >> n;
    int res = (LL)fact[2 * n] * infact[n] % mod * infact[n] % mod * ksm(n + 1, mod - 2) % mod;
    cout << res << endl;
    return 0;
}

作者：番茄酱
链接：https://www.acwing.com/solution/content/8907/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
容斥原理 
给定一个整数 nn 和 mm 个不同的质数 p1,p2,…,pmp1,p2,…,pm。
 
请你求出 1∼n1∼n 中能被 p1,p2,…,pmp1,p2,…,pm 中的至少一个数整除的整数有多少个。
 
输入格式
 
第一行包含整数 nn 和 mm。
 
第二行包含 mm 个质数。
 
输出格式
 
输出一个整数，表示满足条件的整数的个数。
 
数据范围
 
1≤m≤161≤m≤16,
 1≤n,pi≤1091≤n,pi≤109
 
输入样例：
 
10 2
2 3
 
输出样例：
 
7
 
#include
using namespace std;
typedef long long LL;

const int N = 20;
int p[N], n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> p[i];

    int res = 0;
    //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    for(int i = 1; i < 1 << m; i++) {
        int t = 1;             //选中集合对应质数的乘积
        int s = 0;             //选中的集合数量

        //枚举当前状态的每一位
        for(int j = 0; j < m; j++){
            //选中一个集合
            if(i >> j & 1){
                //乘积大于n, 则n/t = 0, 跳出这轮循环
                if((LL)t * p[j] > n){    
                    t = -1;
                    break;
                }
                s++;                  //有一个1，集合数量+1
                t *= p[j];
            }
        }

        if(t == -1) continue;  

        if(s & 1) res += n / t;              //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
        else res -= n / t;                      //反之则为 -1
    }

    cout << res << endl;
    return 0;
}


作者：random_srand
链接：https://www.acwing.com/solution/content/29702/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
 
博弈论 
给定 nn 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
 
问如果两人都采用最优策略，先手是否必胜。
 
输入格式
 
第一行包含整数 nn。
 
第二行包含 nn 个数字，其中第 ii 个数字表示第 ii 堆石子的数量。
 
输出格式
 
如果先手方必胜，则输出 Yes。
 
否则，输出 No。
 
数据范围
 
1≤n≤1051≤n≤105,
 1≤每堆石子数≤1091≤每堆石子数≤109
 
输入样例：
 
2
2 3
 
输出样例：
 
Yes
 
#include 
#include 
using namespace std;



int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}


作者：qiaoxinwei
链接：https://www.acwing.com/solution/content/14269/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
现在，有一个 nn 级台阶的楼梯，每级台阶上都有若干个石子，其中第 ii 级台阶上有 aiai 个石子(i≥1i≥1)。
 
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
 
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
 
问如果两人都采用最优策略，先手是否必胜。
 
输入格式
 
第一行包含整数 nn。
 
第二行包含 nn 个整数，其中第 ii 个整数表示第 ii 级台阶上的石子数 aiai。
 
输出格式
 
如果先手方必胜，则输出 Yes。
 
否则，输出 No。
 
数据范围
 
1≤n≤1051≤n≤105,
 1≤ai≤1091≤ai≤109
 
输入样例：
 
3
2 1 3
 
输出样例：
 
Yes
 
#include 

using namespace std;

int main()
{
    int res = 0;
    int n;
    cin >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        cin >> x;
        if(i % 2) res ^= x;
    }

    if(res) puts("Yes");
    else puts("No");
    return 0;
}
 
给定 nn 堆石子以及一个由 kk 个不同正整数构成的数字集合 SS。
 
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 SS，最后无法进行操作的人视为失败。
 
问如果两人都采用最优策略，先手是否必胜。
 
输入格式
 
第一行包含整数 kk，表示数字集合 SS 中数字的个数。
 
第二行包含 kk 个整数，其中第 ii 个整数表示数字集合 SS 中的第 ii 个数 sisi。
 
第三行包含整数 nn。
 
第四行包含 nn 个整数，其中第 ii 个整数表示第 ii 堆石子的数量 hihi。
 
输出格式
 
如果先手方必胜，则输出 Yes。
 
否则，输出 No。
 
数据范围
 
1≤n,k≤1001≤n,k≤100,
 1≤si,hi≤100001≤si,hi≤10000
 
输入样例：
 
2
2 5
3
2 4 7
 
输出样例：
 
Yes
 
#include
#include
#include
#include

using namespace std;

const int N=110,M=10010;
int n,m;
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值

int sg(int x)
{
    if(f[x]!=-1) return f[x];
    //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
    set S;
    //set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
    for(int i=0;i=sum) S.insert(sg(x-sum));
        //先延伸到终点的sg值后,再从后往前排查出所有数的sg值
    }

    for(int i=0;;i++)
    //循环完之后可以进行选出最小的没有出现的自然数的操作
     if(!S.count(i))
      return f[x]=i;
}

int main()
{
    cin>>m;
    for(int i=0;i>s[i];

    cin>>n;
    memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过

    int res=0;
    for(int i=0;i>x;
        res^=sg(x);
        //观察异或值的变化,基本原理与Nim游戏相同
    }

    if(res) printf("Yes");
    else printf("No");

    return 0;
}

作者：E.lena
链接：https://www.acwing.com/solution/content/23435/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
给定 nn 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 00，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
 
问如果两人都采用最优策略，先手是否必胜。
 
输入格式
 
第一行包含整数 nn。
 
第二行包含 nn 个整数，其中第 ii 个整数表示第 ii 堆石子的数量 aiai。
 
输出格式
 
如果先手方必胜，则输出 Yes。
 
否则，输出 No。
 
数据范围
 
1≤n,ai≤1001≤n,ai≤100
 
输入样例：
 
2
2 3
 
输出样例：
 
Yes
 
#include 
#include 
#include 

using namespace std;

const int N = 110;

int n;
int f[N];
unordered_set S;

int sg(int x)
{
    if(f[x] != -1) return f[x];


    for(int i = 0 ; i < x ; i++)
        for(int j = 0 ; j <= i ; j++)//规定j不大于i，避免重复
            S.insert(sg(i) ^ sg(j));//相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，
                                   //等于这些局面SG值的异或和

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

int main()
{
    memset(f , -1 , sizeof f);

    cin >> n;
    int res = 0;
    while(n--)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if(res) puts("Yes");
    else puts("No");
    return 0;
}

作者：Anoxia_3
链接：https://www.acwing.com/solution/content/13193/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。