AtCoder Beginner Contest 162 C~F

比赛链接：Here

AB水题，

C - Sum of gcd of Tuples (Easy)

题意：#card=math&code=%5Csum%7Ba%3D1%7D%5E%7BK%7D%20%5Csum%7Bb%3D1%7D%5E%7BK%7D%20%5Csum_%7Bc%3D1%7D%5E%7BK%7D%20g%20c%20d%28a%2C%20b%2C%20c%29)

数据范围：

思路：因为 比较小，我们直接跑暴力即可

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n; cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                ans += __gcd(__gcd(i, j), k);
    cout << ans;
}

D - RGB Triplets

题意：给一个长度为N的字符串S，只包含’R’，’B’，’G’。求有多少个三元组 (1%5Cle%20i%3Cj%3Ck%5Cle%20N)#card=math&code=%28i%2Cj%2Ck%29%281%5Cle%20i%3Cj%3Ck%5Cle%20N%29) 满足

数据范围：

题解：先将满足 的算出来，在减去 的数目。

总的显然等于 num(B)num(G)#card=math&code=num%28R%29%2Anum%28B%29%2Anum%28G%29) ，然后枚举两个端点，判断第三个端点是不是不同于这个两个端点的颜色。

const int N = 4e3 + 5;
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; string s;
    cin >> n >> s;
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'R') a += 1;
        if (s[i] == 'G') b += 1;
        if (s[i] == 'B') c += 1;
    }
    ll ans = 1ll * a * b * c;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) continue;
            if (2 * j - i < n && s[i] != s[2 * j - i] && s[j] != s[2 * j - i]) ans--;
        }
    cout << ans;
}

E - Sum of gcd of Tuples (Hard)

题意：(%5Cbmod%201%20%5Cmathrm%7Be%7D%209%2B7)#card=math&code=%5Csum%7Ba%7B1%7D%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7BK%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7BK%7D%20g%20c%20d%5Cleft%28a%7B1%7D%2C%20a%7B2%7D%2C%20%5Cldots%2C%20a_%7BN%7D%5Cright%29%28%5Cbmod%201%20%5Cmathrm%7Be%7D%209%2B7%29)

数据范围：

思路一：莫比乌斯反演化简

%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7BK%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7BK%7D%20i%5Cleft%5B%5Coperatorname%7Bgcd%7D%5Cleft(a%7B1%7D%2C%20a%7B2%7D%2C%20%5Cldots%2C%20a%7BN%7D%5Cright)%3D%3Di%5Cright%5D%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20i%5Cleft%5B%5Coperatorname%7Bgcd%7D%5Cleft(a%7B1%7D%2C%20a%7B2%7D%2C%20%5Cldots%2C%20a%7BN%7D%5Cright)%3D%3D1%5Cright%5D%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20i%20%5Csum%7Bd%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cmu(d)%5Cleft%5Clfloor%5Cfrac%7Bd%7D%7Ba%7B1%7D%7D%5Cright%5Crfloor%5Cleft%5Clfloor%5Cfrac%7Bd%7D%7Ba%7B2%7D%7D%5Cright%5Crfloor%20%5Cldots%5Cleft%5Clfloor%5Cfrac%7Bd%7D%7Ba%20N%7D%5Cright%5Crfloor%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20i%20%5Csum%7Bd%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7B%5Cimath%7D%5Cright%5Crfloor%7D%20%5Cmu(d)%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%7D%20%5Csum%7Ba%202%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%7D%20%5Cldots%20%5Csum%7Ba%20N%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%7D%201%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20i%20%5Csum%7Bd%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cmu(d)%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%5E%7BN%7D%20%5C%5C%0A%3D%5Csum%7BT%3D1%7D%5E%7BK%7D%5Cleft%5Clfloor%5Cfrac%7BK%7D%7BT%7D%5Cright%5Crfloor%5E%7BN%7D%20%5Csum%7Bd%20%5Cmid%20T%7D%20%5Cmu(d)%20*%5Cleft%5Clfloor%5Cfrac%7BT%7D%7Bd%7D%5Cright%5Crfloor(T%3Di%20d)%20%5C%5C%0A%3D%5Csum%7BT%3D1%7D%5E%7BK%7D%5Cleft%5Clfloor%5Cfrac%7BK%7D%7BT%7D%5Cright%5Crfloor%5E%7BN%7D%20%5Cphi(T)%0A%5Cend%7Barray%7D%0A#card=math&code=%5Cbegin%7Barray%7D%7Bl%7D%0AA%20n%20s%3D%5Csum%7Ba%7B1%7D%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7BK%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7BK%7D%20g%20c%20d%5Cleft%28a%7B1%7D%2C%20a%7B2%7D%2C%20%5Cldots%2C%20a%7BN%7D%5Cright%29%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7BK%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7BK%7D%20i%5Cleft%5B%5Coperatorname%7Bgcd%7D%5Cleft%28a%7B1%7D%2C%20a%7B2%7D%2C%20%5Cldots%2C%20a%7BN%7D%5Cright%29%3D%3Di%5Cright%5D%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20i%5Cleft%5B%5Coperatorname%7Bgcd%7D%5Cleft%28a%7B1%7D%2C%20a%7B2%7D%2C%20%5Cldots%2C%20a%7BN%7D%5Cright%29%3D%3D1%5Cright%5D%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Csum%7Ba%7B2%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cldots%20%5Csum%7Ba%7BN%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20i%20%5Csum%7Bd%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cmu%28d%29%5Cleft%5Clfloor%5Cfrac%7Bd%7D%7Ba%7B1%7D%7D%5Cright%5Crfloor%5Cleft%5Clfloor%5Cfrac%7Bd%7D%7Ba%7B2%7D%7D%5Cright%5Crfloor%20%5Cldots%5Cleft%5Clfloor%5Cfrac%7Bd%7D%7Ba%20N%7D%5Cright%5Crfloor%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20i%20%5Csum%7Bd%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7B%5Cimath%7D%5Cright%5Crfloor%7D%20%5Cmu%28d%29%20%5Csum%7Ba%7B1%7D%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%7D%20%5Csum%7Ba%202%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%7D%20%5Cldots%20%5Csum%7Ba%20N%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%7D%201%20%5C%5C%0A%3D%5Csum%7Bi%3D1%7D%5E%7BK%7D%20i%20%5Csum%7Bd%3D1%7D%5E%7B%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%7D%5Cright%5Crfloor%7D%20%5Cmu%28d%29%5Cleft%5Clfloor%5Cfrac%7BK%7D%7Bi%20d%7D%5Cright%5Crfloor%5E%7BN%7D%20%5C%5C%0A%3D%5Csum%7BT%3D1%7D%5E%7BK%7D%5Cleft%5Clfloor%5Cfrac%7BK%7D%7BT%7D%5Cright%5Crfloor%5E%7BN%7D%20%5Csum%7Bd%20%5Cmid%20T%7D%20%5Cmu%28d%29%20%2A%5Cleft%5Clfloor%5Cfrac%7BT%7D%7Bd%7D%5Cright%5Crfloor%28T%3Di%20d%29%20%5C%5C%0A%3D%5Csum_%7BT%3D1%7D%5E%7BK%7D%5Cleft%5Clfloor%5Cfrac%7BK%7D%7BT%7D%5Cright%5Crfloor%5E%7BN%7D%20%5Cphi%28T%29%0A%5Cend%7Barray%7D%0A)

由于 不大，预处理欧拉函数，直接遍历即可。 大的话，整除分块加杜教筛（雾。

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 1e5 + 5, MD = 1e9 + 7;
int pri[N], tot, phi[N];
bool p[N];
void init() {
    p[1] = true, phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!p[i]) pri[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * pri[j] < N; j++) {
            p[i * pri[j]] = true;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % MD) if (b & 1) ans = ans * a % MD;
    return ans;
}
void add(int &x, int y) { x += y; if (x >= MD) x -= MD;}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    init();
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
        add(ans, 1LL * qpow(k / i, n)*phi[i] % MD);
    cout << ans;
}

思路二：

学习了下官方题解：定义 代表 为 的个数，递推关系式：

双重循环即可，里面那层循环的复杂度总和是个调和级数， 级别的。

const int N = 1e5 + 5, MD = 1e9 + 7;
int f[N];
ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % MD) if (b & 1) ans = ans * a % MD;
    return ans;
}
void add(int &x, int y) {
    x += y;
    if (x >= MD) x -= MD;
    if (x < 0) x += MD;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    scanf("%d%d", &n, &k);
    cin >> n >> k;
    for (int i = k; i >= 1; i--) {
        f[i] = qpow(k / i, n);
        for (int j = 2 * i; j <= k; j += i)
            add(f[i], -f[j]);
    }
    int ans = 0;
    for (int i = 1; i <= k; i++)
        add(ans, 1LL * f[i]*i % MD);
    cout << ans;
}

F - Select Half

题意：给一个长度为 的序列 ，要求选 个数，且下标互不相邻，最大化它们的总和。

数据范围：

题解：对于选的数的下标， ，可以发现

因此定义 代表选第 里面的数（必选第个 数），前面多空了 的最大值。

%2Ba%5Bi%5D%20%5C%5C%0Af%5Bi%5D%5B2%5D%20%26%3D%5Cmax%20(f%5Bi-2%5D%5B2%5D%2C%20f%5Bi-3%5D%5B1%5D%2C%20f%5Bi-4%5D%5B0%5D)%2Ba%5Bi%5D%0A%5Cend%7Baligned%7D%5Cright.%0A#card=math&code=%5Cleft%5C%7B%5Cbegin%7Baligned%7D%0Af%5Bi%5D%5B0%5D%20%26%3Df%5Bi-2%5D%5B0%5D%2Ba%5Bi%5D%20%5C%5C%0Af%5Bi%5D%5B1%5D%20%26%3D%5Cmax%20%28f%5Bi-2%5D%5B1%5D%2C%20f%5Bi-3%5D%5B0%5D%29%2Ba%5Bi%5D%20%5C%5C%0Af%5Bi%5D%5B2%5D%20%26%3D%5Cmax%20%28f%5Bi-2%5D%5B2%5D%2C%20f%5Bi-3%5D%5B1%5D%2C%20f%5Bi-4%5D%5B0%5D%29%2Ba%5Bi%5D%0A%5Cend%7Baligned%7D%5Cright.%0A)

const int N = 2e5 + 5;
int a[N];
ll f[N][3];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            f[i][j] = -1e18;
    for (int i = 1; i <= 3; i++)
        f[i][i - 1] = a[i];
    f[3][0] = a[1] + a[3];
    for (int i = 4; i <= n; i++) {
        f[i][0] = f[i - 2][0] + a[i];
        f[i][1] = max(f[i - 2][1], f[i - 3][0]) + a[i];
        f[i][2] = max(f[i - 2][2], f[i - 3][1]) + a[i];
        if (i > 4) f[i][2] = max(f[i][2], f[i - 4][0] + a[i]);
    }
    ll ans;
    if (n & 1) ans = max(f[n][2], max(f[n - 1][1], f[n - 2][0]));
    else
        ans = max(f[n][1], f[n - 1][0]);
    cout << ans;
}