列表

详情


NC219783. NIT的gcd

描述

NIT 在 n 年前还是普及组选手的时候做过这样一个题目,求 以NIT现在国家队的实力,做这样的题实在是太侮辱他的智商了,于是他思考着加强这道题目。

给你一个正整数 n。

请你输出  的值,对  取模。

输入描述

一行 1 个正整数 n,意义见题目。

输出描述

一行 1 个正整数 ans 表示答案,对 998244353 取模。

示例1

输入:

2

输出:

18

说明:

(1,1,1) 贡献为 1,(1,1,2) 贡献为 1,(1,2,1) 贡献为 1,(2,1,1) 贡献为 1

(1,2,2) 贡献为 2,(2,1,2) 贡献为 2,(2,2,1) 贡献为 2,(2,2,2) 贡献为 8

故总答案为 18

示例2

输入:

3

输出:

78

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 2681ms, 内存消耗: 76340K, 提交时间: 2022-06-03 21:59:10

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

const int maxn = 100010, P = 998244353, coef[] = {1, 1, 3, 6};
int n, ans, phi[maxn], deg[maxn], vis[maxn], tmp[maxn];
vector<int> d[maxn], G[maxn];
vector<array<int, 2>> H[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        phi[i] += i;
        for (int j = i + i; j <= n; j += i) phi[j] -= phi[i];
        for (int j = i; j <= n; j += i) d[j].push_back(i);
    }
    auto lcm = [&](int x, int y) {
        return 1LL * x / __gcd(x, y) * y;
    };
    for (int i = 1; i <= n; i++) {
        for (int j : d[i]) for (int k : d[i]) if (j <= k && i == lcm(j, k)) {
            G[j].push_back(k), deg[j]++;
            if (j < k) G[k].push_back(j), deg[k]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j : G[i]) if (make_pair(deg[i], i) <= make_pair(deg[j], j)) {
            H[i].push_back({j, int(n / lcm(i, j))});
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto &j : H[i]) vis[j[0]] = i, tmp[j[0]] = j[1];
        for (auto &j : H[i]) {
            for (auto &k : H[j[0]]) if (i == vis[k[0]]) {
                int a = j[1], b = k[1], c = tmp[k[0]];
                ans = (ans + 1LL * phi[i] * phi[j[0]] % P * phi[k[0]] % P * a % P * b % P
                    * c % P * coef[(i != j[0]) + (j[0] != k[0]) + (i != k[0])]) % P;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

上一题