abc 281 D

本质上还是01背包问题，只是需要细分它的状态，比如物品数量和总和余数
总之，表示出装 i 个物品， 价值总和余数为 j 的状态
然后用01背包的方法，将物品放入，得到dp[K][0] 即为答案

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

    int N, K, D;
    cin >> N >> K >> D;
    vector<int> a(N);
    for (int i = 0; i < N; i ++) cin >> a[i];

    vector<vector<ll>> dp(K + 1, vector<ll> (D, -1));
    dp[0][0] = 0;

    // for (int i = 0; i < N; i ++) {
    //     for (int j = K; j >= 1; j --) {
    //         for (int k = 0; k < D; k ++) {
    //             if (~dp[j - 1][(k + D - a[i] % D) % D]) dp[j][k] = max(dp[j - 1][(k + D - a[i] % D) % D] + a[i], dp[j][k]);
    //         }
    //     }
    // }

    for (int i = 0; i < N; i ++) {
        for (int j = K - 1; j >= 0; j --) {
            for (int k = 0; k < D; k ++) {
                if (dp[j][k] == -1) continue;
                dp[j + 1][(k + a[i] % D) % D] = max(dp[j][k] + a[i], dp[j + 1][(k + a[i] % D) % D]);
            }
        }
    }

    cout << dp[K][0] << endl;

    return 0;
}

abc 280 D

时间复杂度 O(sqrt(n))，如果无法在 6000000 下将它归为 1，则说明必须阶乘到本身才能得到 1
每回除以 gcd，大于 sqrt(n) 的因子只有一个，所以枚举到 6000000，所有可以枚举的都枚举到了
还有一个数，说明是质数，因为能除掉的早被除掉了，所以输出此时的 k
这个算是比较巧妙的方法了
也可以将sqrt(k) <= k 的质因数都分解出来，然后处理一下质因数的指数和答案的关系
即提供 e 个贡献的数的值，因为如果是 p 的幂，提供了指数个贡献
答案是这个数的最大值
如果sqrt(k) 都枚举完了 k 还不为 1，则说明有一个大的质因数，再将这个和答案比较一下，输出较大值 

abc 279 D

二分
不知道为什么，在本地精确度不够，但 AC 了

abc 278 D

本以为考初始化值的时间复杂度
新建一个vector然后赋值，或者fill都会超时因为初始化的时间复杂度只有O(n)的
那么给一个记录整体修改次数的vector
如果修改时间小于当前，那这个值就是整体赋的值
然后用的时候更新一下

abc 277 D

离散化 + 约瑟夫环的经典方案，可以避免特判

abc 276 D

模拟 + gcd