给定\(A_1,A_2,\dots,A_N\)，求\(\sum_{i=1}^N\sum_{j=1}^Nlcm(A_i,A_j)\)
\(1\le N\le 50000;1\le A_i\le 50000\)
为了推式子方便我们设：
\(n=50000\) \(a_i=\sum_{j=1}^N[A_j=i]\)
答案就是\(\sum_{i=1}^n\sum_{j=1}^na_ia_jlcm(i,j)\)
\(\sum_{i=1}^n\sum_{j=1}^na_ia_jlcm(i,j)\)
\(=\sum_{i=1}^n\sum_{j=1}^na_ia_j\frac{ij}{\gcd(i,j)}\)
\(=\sum_{p=1}^n\frac1p\sum_{i=1}^n\sum_{j=1}^na_ia_jij[\gcd(i,j)=p]\)
\(=\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}a_{ip}a_{jp}ij[\gcd(i,j)=1]\)
\(=\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}a_{ip}a_{jp}ij\sum_{d|i,d|j}\mu(d)\)
\(=\sum_{p=1}^np\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{n/dp}\sum_{j=1}^{n/dp}a_{idp}a_{jdp}ij\)
\(=\sum_{q=1}^nq\sum_{d|q}d\mu(d)\sum_{i=1}^{n/q}\sum_{j=1}^{n/q}a_{iq}a_{jq}ij\)
\(=\sum_{q=1}^nq\sum_{d|q}d\mu(d)\left(\sum_{i=1}^{n/q}a_{iq}i\right)^2\)
\(\sum_{i=1}^{n/q}a_{iq}i\)对于每个\(q\)求值，总复杂度为\(\frac n 1+\frac n 2+\frac n 3+\dots+\frac nn\)复杂度为调和级数\(O(n\log n)\)
前半部分筛\(d\)后枚举\(d\)及其倍数，复杂度还是调和级数\(O(n\log n)\)
然后直接求和就行了，貌似不用打数论分块
41行一遍A。。。真不用打数论分块，复杂度nlogn
#includeusing namespace std;int prime[50010], mu[50010], tot, fuck = 50000;bool vis[50010];long long sum1[50010], sum2[50010];int bucket[50010];int main(){ mu[1] = 1; for (int i = 2; i <= fuck; i++) { if (vis[i] == false) prime[++tot] = i, mu[i] = -1; for (int j = 1; j <= tot && i * prime[j] <= fuck; j++) { vis[i * prime[j]] = true; if (i % prime[j] == 0) break; mu[i * prime[j]] = -mu[i]; } mu[i] *= i; } for (int d = 1; d <= fuck; d++) for (int q = d; q <= fuck; q += d) sum1[q] += mu[d]; for (int i = 1; i <= fuck; i++) sum1[i] *= i; int n; scanf("%d", &n); for (int x, i = 1; i <= n; i++) scanf("%d", &x), bucket[x]++; long long ans = 0; for (int q = 1; q <= fuck; q++) { int sb = fuck / q; for (int i = 1; i <= sb; i++) sum2[q] += bucket[i * q] * (long long)i; ans += sum2[q] * sum1[q] * sum2[q]; } printf("%lld\n", ans); return 0;}