https://www.51nod.com/Challenge/Problem.html#!#problemId=1188
求(sumlimits_{i=1}^{n-1}sumlimits_{j=i+1}^{n}gcd(i,j))
首先交换求和(sumlimits_{j=2}^{n}sumlimits_{i=1}^{j-1}gcd(i,j)=sumlimits_{j=2}^{n}sumlimits_{i=1}^{j}gcd(i,j)-j)
像之前那样用莫比乌斯反演搞出
(sumlimits_{g=1}^{n}gsumlimits_{i=1}^{lfloorfrac{n}{g}
floor}{varphi(i)}, (varphi(1)=0))
或者
(sumlimits_{g=1}^{n}gsumlimits_{i=1}^{lfloorfrac{n}{g}
floor}{mu(i)}*{lfloorfrac{n}{i*g}
floor}^2)
都是T了，说明单次回答的复杂度非常感人，原因是因为跟n有关就逃不了分块。
所以分块的复杂度还是太高了。
然后惊人的事情发生了。
这道题和前面的不一样的地方在于，他的n其实没有前面的大，只是多！
分块的意义在于加快单次回答的速度，所以才把g提了出来分块，现在不太合适。
正解，先求解：
(sumlimits_{i=1}^{n}gcd(i,n))
这个东西可以枚举g：
(sumlimits_{g=1}^{n}gsumlimits_{i=1}^{n}[gcd(i,n)==g])
(sumlimits_{g=1}^{n}gsumlimits_{i=1}^{lfloorfrac{n}{g}
floor}[gcd(i,lfloorfrac{n}{g}
floor)==1])
(sumlimits_{g=1}^{n}gvarphi(lfloorfrac{n}{g}
floor))
这个有什么不对呢？其实没什么不对，就是不好。因为gcd必定是整除n的，所以可以：
(sumlimits_{g|n}gvarphi(frac{n}{g}))
这明显就是一个积性函数，记为 (p(n)) ，处理好就可以了。原式：
(sumlimits_{j=2}^{n}p(j)-j)
这个式子 (p(n)) 用埃筛已经足够了，因为是5e6的数据量，1400ms/2000ms跑过去了。但是我在想会不会有线性的筛法。
2019/6/7早上试了很多种之后，发现还是直接利用积性函数的结论最简单，对于每个合数记录他的最小质因子及其幂次，然后一除就得到两个互质的因数。
问题在于纯p的幂次一除就变成没有了。也就是别人的博客说的 (p^k) 要特殊处理，想到上面这个式子是一个狄利克雷卷积，对于纯p的幂次只要从他的低1次转移过来就可以了。
最后套上快读快写狗掉榜首！需要注意的是我准备的线性筛模板里多用了0.25倍空间，其实真的可以充分利用的。比如这个的话pk肯定不是0，那么就用pk来做判断就可以了。
所以说的确是空间换时间，多了0.5倍的空间省去一个logn倍。200ms/2000ms稳得一笔。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
do {
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
} while(c>='0'&&c<='9');
return x;
}
inline void write(ll x) {
//printf("%lld
",x);
if(x>9) {
write(x/10);
}
putchar(x%10+'0');
return;
}
const int MAXN=5e6;
int pri[MAXN+1];
int &pritop=pri[0];
ll ans[MAXN+1];
int pk[MAXN+1];//pk(n)=pk的最小因子p的次方
void sieve(int n=MAXN) {
ans[1]=1;
pk[1]=1;
for(int i=2; i<=n; i++) {
if(!pk[i]) {
pri[++pritop]=i;
ans[i]=i+i-1;
pk[i]=i;
}
for(int j=1; j<=pritop&&i*pri[j]<=n; j++) {
int t=i*pri[j];
if(i%pri[j]) {
pk[t]=pk[pri[j]];
ans[t]=ans[i]*ans[pri[j]];
} else {
pk[t]=pk[i]*pri[j];
if(pk[t]==t) {
//纯p的幂次，没有其他因子，这样算不会漏因子
//t-t/pri[j]就是phi[t]
ans[t]=(t-t/pri[j])+ans[i]*pri[j];
} else {
//积性函数
ans[t]=ans[pk[t]]*(ans[t/pk[t]]);
}
break;
}
}
}
for(int i=1; i<=n; i++)
ans[i]+=ans[i-1]-i;
}
inline void solve() {
sieve();
int T=read();
while(T--) {
int n=read();
write(ans[n]);
putchar('
');
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in","r",stdin);
#endif // Yinku
solve();
return 0;
}
其他尝试？
现在把g放回去。
(sumlimits_{g=1}^{n}sumlimits_{i=1}^{lfloorfrac{n}{g}
floor}g*{varphi(i)}, (varphi(1)=0))
这个不就是相当于把每个 (i*g leq n) 的加起来吗？所以当然可以交换求和顺序！
(sumlimits_{i=1}^{n}sumlimits_{g=1}^{lfloorfrac{n}{i}
floor}g*{varphi(i)}, (varphi(1)=0))
前面是一个干净的前缀和，后面那个式子是nlogn的！
也就是预处理：
(ans(n)=sumlimits_{g=1}^{lfloorfrac{n}{i}
floor}g*{varphi(i)}, (varphi(1)=0))