40 · 回顾七：DP 与数论

设 f[j] = 用不超过 j 的时间能拿到的最大价值，初值全 0（什么都不采，价值 0）。

对每株草药 i：不采它，f[j] 不变；采它，f[j] = f[j − t[i]] + v[i]。两者取大。

容量必须倒序枚举。正序时 f[j − t[i]] 已经被第 i 株更新过，等于允许同一株采两次，答案偏大。

答案就是 f[T]，复杂度 O(M·T) = 10⁵，时间与空间都宽松。

#include <bits/stdc++.h>
using namespace std;

int T, M;
int t[105], v[105];
int f[1005];                        // f[j]：时间不超过 j 时的最大价值

int main() {
    cin >> T >> M;
    for (int i = 1; i <= M; ++i) cin >> t[i] >> v[i];

    for (int i = 1; i <= M; ++i)
        for (int j = T; j >= t[i]; --j)          // 倒序：保证每株草药只用一次
            f[j] = max(f[j], f[j - t[i]] + v[i]);

    cout << f[T] << "\n";
    return 0;
}

断环成链：把 a 复制一份，a[i + n] = a[i]。于是任何长度为 n 的连续区间都对应环上的一种合并顺序。

设 f[i][j] 表示把第 i..j 颗珠子合并成一颗的最大能量。最后一次合并把区间分成 [i,k] 与 [k+1,j]，合并后的左块是 (a[i], a[k+1])，右块是 (a[k+1], a[j+1])，释放 a[i] × a[k+1] × a[j+1]。

转移：枚举断点 k，f[i][j] = max( f[i][k] + f[k+1][j] + a[i]·a[k+1]·a[j+1] )。

答案 = max f[i][i+n−1]（i = 1…n），因为环有 n 种断法。复杂度 O(n³) = 10⁶。

#include <bits/stdc++.h>
using namespace std;

int n, a[205];
long long f[205][205];      // f[i][j]：把第 i..j 颗珠子合成一颗的最大能量

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i + n] = a[i]; }  // 断环成链

    for (int len = 2; len <= n; ++len)                  // 长度从小到大，保证小区间先算
        for (int i = 1; i + len - 1 < 2 * n; ++i) {     // 右端点 j <= 2n-1：能量要用 a[j+1]，j = 2n 就越界
            int j = i + len - 1;
            for (int k = i; k < j; ++k)                 // 最后一次合并的断点
                f[i][j] = max(f[i][j],
                              f[i][k] + f[k + 1][j] + 1LL * a[i] * a[k + 1] * a[j + 1]);
        }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i][i + n - 1]);   // n 种断法
    cout << ans << "\n";
    return 0;
}

先筛出 b 以内的所有质数（埃氏筛），再对每个质数判回文。

关键剪枝：偶数位的回文数一定能被 11 整除，所以 8 位数的回文数全都不是质数；b ≤ 10⁸ 时 9 位数只有 100000000，它不是回文。于是 b 可以直接截到 9999999，1 亿的筛法变成 1 千万，时间空间都省一个量级。

筛法：comp[i] 表示 i 被标记为合数；i 未标记就是素数，把 i²、i²+i、… 全部标记。内层循环的起点必须是 i²，否则 10⁷ 的筛法会退化成 O(n log n) 且常数很大。

判回文用整数翻转：把 x 的十进制位翻过来，和原数比较，空间 O(1)，比转字符串快。

#include <bits/stdc++.h>
using namespace std;

const int N = 10000005;
bool comp[N];                       // comp[i] = true 表示 i 是合数

bool pal(int x) {                   // 判回文：翻过来看是否相等
    int t = x, r = 0;
    while (t) { r = r * 10 + t % 10; t /= 10; }
    return r == x;
}

int main() {
    int a, b;
    cin >> a >> b;
    b = min(b, 9999999);            // 8 位回文数必被 11 整除，截掉它们不丢答案

    for (int i = 2; i <= b; ++i) {
        if (!comp[i]) {             // i 没被标记 → i 是素数
            if (i >= a && pal(i)) cout << i << "\n";
            for (long long j = 1LL * i * i; j <= b; j += i)
                comp[j] = true;     // 从 i*i 开始标记，更小的倍数早被筛过
        }
    }
    return 0;
}

由 gcd(P,Q) · lcm(P,Q) = P · Q 得 P·Q = x₀·y₀。x₀ 不整除 y₀ 时无解。

令 P = x₀·i、Q = x₀·j，代入 P·Q = x₀·y₀ 得 i·j = y₀/x₀ = n。

gcd(P,Q) = x₀·gcd(i,j)，要求等于 x₀，所以 gcd(i,j) = 1。于是问题变成：枚举 n 的因子对 (i, j)，数其中互质的有几对。

枚举到 √n 即可：每找到一个因子 i 就得到一对 (i, n/i)，互质则答案加 2（(i,j) 和 (j,i)）；i == n/i 时只加 1，避免重复。复杂度 O(√n)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x, y;
    cin >> x >> y;

    if (y % x) { cout << 0 << "\n"; return 0; }   // x 不整除 y，无解
    long long n = y / x, ans = 0;

    for (long long i = 1; i * i <= n; ++i) {
        if (n % i) continue;                     // i 不是 n 的因子
        long long j = n / i;
        if (__gcd(i, j) == 1)                    // i、j 互质，还原出的 P、Q 的 gcd 才恰好是 x
            ans += (i == j) ? 1 : 2;             // 有序对：(i,j) 与 (j,i) 各算一次
    }

    cout << ans << "\n";
    return 0;
}

杨辉三角只保留模 k 的余数：C[i][j] = (C[i−1][j−1] + C[i−1][j]) % k。余数为 0 就是 k 的倍数。

把“C[i][j] 是 k 的倍数”记成 0/1 矩阵 bad[i][j]，并把 j > i 的格子强制置 0。这样矩形 [0..n] × [0..min(n,m)] 的和就恰好是答案——多出来的 j > i 格子贡献为 0。

对 bad 做二维前缀和：s[i][j] = bad[i][j] + s[i−1][j] + s[i][j−1] − s[i−1][j−1]。每次询问 O(1)。

预处理 O(N²) ≈ 4×10⁶，询问 O(1)，总复杂度由预处理决定，完全够用。

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
int t, k;
int C[N][N];        // 杨辉三角模 k 的余数
int s[N][N];        // bad 的二维前缀和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> k;

    for (int i = 0; i < N; ++i) {
        C[i][0] = C[i][i] = 1 % k;              // 两条边界：C(i,0) = C(i,i) = 1
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;   // 只要余数
    }

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            int bad = (j <= i && C[i][j] == 0) ? 1 : 0;      // j > i 不是合法组合数
            s[i][j] = bad;
            if (i) s[i][j] += s[i - 1][j];
            if (j) s[i][j] += s[i][j - 1];
            if (i && j) s[i][j] -= s[i - 1][j - 1];          // 二维容斥
        }

    while (t--) {
        int n, m;
        cin >> n >> m;
        if (m > n) m = n;                       // 题目要求 j <= min(i, m)
        cout << s[n][m] << "\n";
    }
    return 0;
}