[题解] LuoguP6055 [RC-02] GCD

https://www.luogu.com.cn/problem/P6055

给一个(n)，让你求

[sumlimits_{i=1}^n sumlimits_{j=1}^n sumlimits_{p=1}^{lfloor n/j floor} sumlimits_{q=1}^{lfloor n/j floor} [gcd(i,j)=1][gcd(p,q)=1] ]

观察到后面两个下取整

[sumlimits_{p=1}^{lfloor n/j floor}sumlimits_{q=1}^{lfloor n/j floor} [gcd(p,q)=1] ]

把(p,q)都乘上(j)，然后就等于

[sumlimits_{p=1}^n sumlimits_{q=1}^n [gcd(p,q)=j] ]

所以我们枚举(p,q)，就可以得到(j=gcd(p,q))，然后

[Ans=sumlimits_{i=1}^n sumlimits_{p=1}^n sumlimits_{q=1}^n [gcd(i,gcd(p,q))=1]=sumlimits_{i=1}^n sumlimits_{p=1}^n sumlimits_{q=1}^n [gcd(i,p,q)=1] ]

然后无脑推一波柿子

[egin{aligned}Ans&=sumlimits_{i=1}^nsumlimits_{p=1}^n sumlimits_{q=1}^n sumlimits_{dmid gcd} mu(d)\&=sumlimits_{d=1}^n mu(d) sumlimits_{i=1}^n [d mid i] sumlimits_{p=1}^n [d mid p]sumlimits_{q=1}^n [dmid q]\ &=sumlimits_{d=1}^n mu(d) lfloorfrac{n}{d} floor^3end{aligned} ]

然后就可以数论分块，但发现(n le 10^9)不怎么好直接筛前缀和，于是杜教筛(mu)前缀和就好了。

跑的贼慢的代码......

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int mu[20000010], ps[20000010], pn = 0;
bool vis[20000010];

void sieve() {
  int n = 20000000; mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) ps[pn++] = i, mu[i] = -1;
    for (int j = 0; j < pn && i * ps[j] <= n; j++) {
      vis[i * ps[j]] = 1;
      if (i % ps[j] == 0) { mu[i * ps[j]] = 0; break; }
      else mu[i * ps[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= n; i++) mu[i] += mu[i-1];
  for (int i = 1; i <= n; i++) if (mu[i] < 0) mu[i] += mod;
}

map<int,int> musum;

int Smu(int n) {
  if (n <= 20000000) return mu[n];
  if (musum.count(n)) return musum[n];
  int ans = n >= 1;
  for (int l = 2, r = 0; l <= n; l = r+1) {
    r = n / (n / l);
    ans -= 1ll * Smu(n / l) * (r - l + 1) % mod;
    if (ans < 0) ans += mod;
  }
  return musum[n] = ans;
}

int ans, n;

int main() {
  sieve();
  scanf("%d", &n);
  for (int l = 1, r = 0; l <= n; l = r+1) {
    r = n / (n / l);
    ans += 1ll * (n/l) * (n/l) % mod * (n/l) % mod * (Smu(r) - Smu(l - 1) + mod) % mod;
    if (ans > mod) ans -= mod;
  }
  printf("%d
", ans);
  return 0;
}