题解

本文档包含了六个算法问题的详细题解，涵盖组合数学、数论、容斥原理、素数筛选、快速幂等核心算法。

---

题目概览

题号	题目名称	核心算法
A	计算系数	二项式定理 + 组合数预处理 + 快速幂
B	平方和	数学公式 + 费马小定理求逆元
C	Co-prime	质因数分解 + 容斥原理
D	Prime Cuts	欧拉筛 + 区间裁剪
E	Pseudoprime numbers	素数判定 + 快速幂
F	Sequence	组合数递推 + 卷积思想

---

Problem A: 计算系数

题意简述

给定多项式 $(ax+by{)}^k$，请求出展开后 $x^n{y}^m$ 项的系数。其中 $a,b,k,n,m$ 均为整数，结果对 $10007$ 取模。

核心思路

根据二项式定理，$(ax+by{)}^k$ 的展开通项为：

$$T_n=\left(\genfrac{}{}{0ex}{}{k}{n}\right)(ax{)}^n(by{)}^{k-n}=\left(\genfrac{}{}{0ex}{}{k}{n}\right)a^n{b}^{k-n}{x}^n{y}^{k-n}$$

题目保证 $n+m=k$，因此 $x^n{y}^m$ 项的系数为：

$$\boxed{\left(\genfrac{}{}{0ex}{}{k}{n}\right)\cdot a^n\cdot b^m\mathrm{mod}10007}$$

代码要点

const int N = 1005;
const int mod = 10007;
int C[N][N];

// 预处理组合数（杨辉三角）
void getC() {
    for (int i = 0; i < N; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
        }
    }
}

// 快速幂
int fastpower(int base, int power) {
    int res = 1;
    while (power) {
        if (power & 1) res = res * base % mod;
        base = base * base % mod;
        power >>= 1;
    }
    return res;
}

// 主函数计算
int ans = C[k][n] * fastpower(a, n) % mod * fastpower(b, m) % mod;

复杂度分析

• 预处理组合数：$O(N^2)$，其中 $N=1005$
• 单次查询：$O(\log n+\log m)$
• 空间复杂度：$O(N^2)$

---

Problem B: 平方和

题意简述

给定 $n$，求：

$$\sum _{i=1}^n{i}^2=1^2+2^2+\cdots +n^2(\mathrm{mod}10^9+7)$$

核心思路

使用平方和公式：

$$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$

由于模数 $10^9+7$ 是质数，且 $6$ 与模数互质，可以用费马小定理求 $6$ 的逆元：

$$6^{-1}\equiv 6^{10^9+5}(\mathrm{mod}10^9+7)$$

代码实现

#include <iostream>
using namespace std;
#define int long long
const int mod = 1000000007;

int fastpower(int base, int power) {
    int res = 1;
    while (power) {
        if (power & 1) res = res * base % mod;
        base = base * base % mod;
        power >>= 1;
    }
    return res;
}

signed main() {
    int n;
    cin >> n;
    int inv6 = fastpower(6, mod - 2);  // 费马小定理求逆元
    int ans = n % mod * ((n + 1) % mod) % mod * ((2 * n + 1) % mod) % mod * inv6 % mod;
    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(\log mod)$，仅需一次快速幂
• 空间复杂度：$O(1)$

---

Problem C: Co-prime

题意简述

给定数 $N$，统计闭区间 $[A,B]$ 中有多少个整数与 $N$ 互质。

核心思路

互质的定义：$\gcd (x,N)=1$。

区间统计通常转化为前缀和：

$$\text{Ans}=f(B)-f(A-1)$$

其中 $f(x)$ 表示 $[1,x]$ 中与 $N$ 互质的数的个数。

容斥原理：用 $N$ 的所有不同质因子，计算 $[1,x]$ 中能被这些质因子整除的数的个数，然后用总数减去。

设 $N$ 的不同质因子集合为 {p1,p2,…,pk}\{p_1, p_2, \dots, p_k\}{p1​,p2​,…,pk​}，则：

$$f(x)=x-\sum _i\lfloor \frac{x}{p_i}\rfloor +\sum _{i<j}\lfloor \frac{x}{p_i{p}_j}\rfloor -\cdots$$

代码实现

ll calc(ll x, vector<int>& p) {
    int sz = p.size();
    ll ans = 0;
    // 枚举所有子集
    for (int mask = 1; mask < (1 << sz); mask++) {
        ll t = 1;
        int bits = 0;
        for (int i = 0; i < sz; i++) {
            if (mask & (1 << i)) {
                if (t * p[i] > x) { t = 0; break; }
                t *= p[i];
                bits++;
            }
        }
        if (t) {
            if (bits & 1) ans += x / t;   // 奇数个因子，加
            else ans -= x / t;            // 偶数个因子，减
        }
    }
    return x - ans;  // 总数减去不互质的个数
}

复杂度分析

• 质因数分解：$O(\sqrt{N})$
• 容斥计算：$O(2^k)$，其中 $k$ 为不同质因子个数（$N\le 10^9$ 时 $k\le 9$）
• 时间复杂度可接受

---

Problem D: Prime Cuts

题意简述

从 $1$ 到 $N$ 之间的质数列表（注意：本题把 $1$ 也视为质数）中，裁剪出中间若干个质数并输出。

若质数总数为偶数，则输出中间 $2c$ 个；若为奇数，则输出中间 $2c-1$ 个。

核心思路

1. 使用欧拉线性筛筛选出 $[1,N]$ 内的所有素数（包含 $1$）
2. 根据 $sz$（素数个数）的奇偶性确定要输出的个数：
   • 奇数：$cnt=2c-1$
   • 偶数：$cnt=2c$
3. 若 $cnt\ge sz$，则输出全部素数
4. 否则，从中间位置开始截取 $cnt$ 个

代码实现

void get_prime() {
    primes.clear();
    memset(vis, false, sizeof vis);
    primes.push_back(1);          // 题目特殊要求
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) primes.push_back(i);
        for (int j = 1; j < primes.size() && 1LL * i * primes[j] <= n; j++) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 主逻辑
int sz = primes.size();
if (sz & 1) c = 2 * c - 1;
else c <<= 1;

if (c >= sz) {
    // 输出全部
} else {
    int st = (sz - c) >> 1;      // 起始位置
    for (int i = st; i < st + c; i++) cout << " " << primes[i];
}

输出格式注意

每个测试用例输出后需跟两个换行符（\n\n）。

---

Problem E: Pseudoprime numbers

题意简述

给定 $2<p\le 10^9$ 和 $1<a<p$，判断 $p$ 是否是以 $a$ 为底的伪素数。

伪素数定义：$p$ 本身是合数，但满足 $a^p\equiv a(\mathrm{mod}p)$。

核心思路

1. 先判断 $p$ 是否为素数，若为素数则直接输出 no
2. 若 $p$ 为合数，用快速幂计算 $a^p\mathrm{mod}p$
3. 若 $a^p\equiv a(\mathrm{mod}p)$，则为伪素数，输出 yes；否则输出 no

代码实现

bool isprime(ll x) {
    if (x < 2) return false;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

ll fastpower(ll base, ll power, ll mod) {
    ll ans = 1;
    while (power) {
        if (power & 1) ans = ans * base % mod;
        base = base * base % mod;
        power >>= 1;
    }
    return ans;
}

// 判断逻辑
if (isprime(p)) {
    cout << "no\n";
} else {
    if (fastpower(a, p, p) == a) cout << "yes\n";
    else cout << "no\n";
}

注意事项

• $p$ 的范围达 $10^9$，$O(\sqrt{p})$ 的素性判断可行（$31623$ 次循环）
• 不能使用费马小定理的逆命题（因为 $p$ 是合数）

---

Problem F: Sequence

题意简述

给定序列 $A(1),A(2),\dots ,A(n)$，定义新序列 $B$：

$$B(i)=A(i)+2A(i-1)+3A(i-2)+\cdots +iA(1)$$

即 $B(i)={\sum }_{j=1}^i(i-j+1)\cdot A(j)$。

现在给定 $k$，需要计算：

$$\sum _{j=1}^i\left(\genfrac{}{}{0ex}{}{k+i-j-1}{i-j}\right)A(j)$$

核心思路

观察递推关系。考虑生成函数或组合恒等式，实际上系数可以通过以下递推计算：

设 $K_i=\left(\genfrac{}{}{0ex}{}{k+i-1}{i}\right)$，则：

$$K_i=K_{i-1}\cdot \frac{k+i-1}{i}$$

用模逆元处理除法。

最终：

$$B(i)=\sum _{j=0}^{i}A(j)\cdot K_{i-j}$$

这是一个卷积的形式，但 $n\le 300$，可以用 $O(n^2)$ 直接计算。

代码实现

const int N = 305;
const ll mod = 1e9 + 7;
ll inv[N], karr[N];

void solve() {
    // 预处理逆元
    inv[0] = inv[1] = 1;
    for (int i = 2; i < N; i++) {
        inv[i] = mod - mod / i * inv[mod % i] % mod;
    }
    
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> a[i];
        cin >> k;
        
        // 计算组合数系数 K_i = C(k + i - 1, i)
        karr[0] = 1;
        for (int i = 1; i < n; i++) {
            ll tmp = (2 * k + i - 1) % mod;   // 注意递推公式
            karr[i] = tmp * karr[i - 1] % mod * inv[i] % mod;
        }
        
        // 卷积计算
        vector<ll> ans(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                ans[i] = (ans[i] + a[j] * karr[i - j]) % mod;
            }
        }
        
        // 输出
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
}

数学推导

原式：

$$B(i)=\sum _{j=1}^i\left(\genfrac{}{}{0ex}{}{k+i-j-1}{i-j}\right)A(j)$$

令 $t=i-j$，则：

$$B(i)=\sum _{t=0}^{i-1}\left(\genfrac{}{}{0ex}{}{k+t-1}{t}\right)A(i-t)$$

所以系数序列为 $K_t=\left(\genfrac{}{}{0ex}{}{k+t-1}{t}\right)$，满足：

$$K_t=\frac{(k+t-1)!}{t!(k-1)!}$$

递推关系：

$$K_t=K_{t-1}\cdot \frac{k+t-1}{t}$$

使用模逆元实现递推。

---

总结

题目	核心知识点	易错点
A	二项式定理、组合数	取模运算的顺序
B	数学公式、费马小定理	模逆元的使用
C	容斥原理、质因数分解	区间转换、子集枚举
D	欧拉筛、区间裁剪	包含1、输出格式
E	快速幂、素性判断	费马小定理不可逆用
F	组合数递推、卷积	模运算下的逆元处理

以上六题覆盖了算法竞赛中常见的数论与组合数学题型，建议掌握其核心思想以应对类似问题。