NC219783. NIT的gcd
描述
给你一个正整数 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; }