易得 $sumlimits_{g=1}^{n} g sumlimits_{k=1}^{n} mu(k) lfloorfrac{n}{gk}
floor lfloorfrac{n}{gk}
floor $
记 (T=gk) 枚举 (T) ，注意这里既然满足 (T=gk) 要保证两个乘起来确实是 (T) ，选择把 (k) 换成 $frac{T}{g} $ .
$sumlimits_{T=1}^{n} lfloorfrac{n}{T}
floor lfloorfrac{n}{T}
floor sumlimits_{g|T} gmu(frac{T}{g}) $
$sumlimits_{T=1}^{n} lfloorfrac{n}{T}
floor lfloorfrac{n}{T}
floor varphi(T) $
猜了一下每次回答都是根号，可能可以，但是交上去T了。原来这个时限是200ms，太惊人了，这道题卡掉了所有其他的思路。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1000000;
int prime[MAXN+1];
int &ptop=prime[0];
ll Phi[MAXN+1];
inline void sieve(){
const int &n=MAXN;
Phi[1]=1;
for(int i=2;i<=n;i++){
if(!Phi[i]){
ptop++;
prime[ptop]=i;
Phi[i]=i-1;
}
for(int j=1;j<=ptop;j++){
int &p=prime[j];
if(i*p>n)
break;
if(i%p){
Phi[i*p]=Phi[i]*Phi[p];
}
else{
Phi[i*p]=Phi[i]*p;
break;
}
}
}
for(int i=1;i<=n;i++){
Phi[i]+=Phi[i-1];
}
}
inline ll H(int n){
ll res=0;
for(int l=1,r;l<=n;l=r+1){
int t=n/l;
r=n/t;
res+=1ll*t*t*(Phi[r]-Phi[l-1]);
}
return res;
}
inline ll G(int n){
ll res=(H(n)-1ll*n*(n+1)/2)/2;
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in","r",stdin);
#endif // Yinku
sieve();
int n;
while(~scanf("%d",&n)){
if(n==0)
break;
else{
printf("%lld
",G(n));
}
}
}
问题在哪里？莫比乌斯反演不擅长进行多次回答，观察题目的数据可能想让我们用埃筛？
回到上面的式子。
其实因为是 (n==m) ，上面的反演很多余，枚举 (g) 的时候可以发现另一个公式，但是好像复杂度也是一样的，先留着，这个也是可以用杜教筛跑出大数据，应该比反演要快（因为这样大的Phi是比上面的少的）。
易得 $sumlimits_{g=1}^{n} g sumlimits_{i=1}^{lfloorfrac{n}{g}
floor} 2varphi(i) - 1 $
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1000000;
int prime[MAXN+1];
int &ptop=prime[0];
ll Phi[MAXN+1];
inline void sieve(){
const int &n=MAXN;
Phi[1]=1;
for(int i=2;i<=n;i++){
if(!Phi[i]){
ptop++;
prime[ptop]=i;
Phi[i]=i-1;
}
for(int j=1;j<=ptop;j++){
int &p=prime[j];
if(i*p>n)
break;
if(i%p){
Phi[i*p]=Phi[i]*Phi[p];
}
else{
Phi[i*p]=Phi[i]*p;
break;
}
}
}
for(int i=1;i<=n;i++){
Phi[i]+=Phi[i-1];
}
}
inline ll s1(ll l,ll r){
return (l+r)*(r-l+1)/2;
}
inline ll H(int n){
ll res=0;
for(int l=1,r;l<=n;l=r+1){
int t=n/l;
r=n/t;
res+=(2ll*Phi[t]-1)*s1(l,r);
}
return res;
}
inline ll G(int n){
ll res=(H(n)-1ll*n*(n+1)/2)/2;
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in","r",stdin);
#endif // Yinku
sieve();
int n;
while(~scanf("%d",&n)){
if(n==0)
break;
else{
printf("%lld
",G(n));
}
}
}
一切从头开始，我们学习反演还有这些东西的初衷是想要降低单次回答的复杂度，看到原来的问题：
$ G(n) = sumlimits_{i=1}^{n-1}sumlimits_{j=i+1}^{n} gcd(i,j) (
交换求和，这个没问题：
) G(n) = sumlimits_{j=2}^{n}sumlimits_{i=1}^{j-1} gcd(i,j) $
记 $ H(n) = sumlimits_{i=1}^{n-1} gcd(i,n) $
原式 (G(n) = sumlimits_{j=2}^{n} H(j))
貌似 (H(n)) 好像似曾相识？ $ H(n) = ( sumlimits_{i=1}^{n} gcd(i,n) ) - n$
里面这个不是前几天处理过？这种 (gcd) 就只可能是 (n) 的因子：
$ H(n) = ( sumlimits_{d|n} d sumlimits_{i=1}^{n} [gcd(i,n)d] ) - n$
$ H(n) = ( sumlimits_{d|n} d sumlimits_{i=1}^{frac{n}{d}} [gcd(i,frac{n}{d})1] ) - n$
$ H(n) = ( sumlimits_{d|n} d varphi(frac{n}{d}) ) - n$
为方便，记 $ h(n) = sumlimits_{d|n} d varphi(frac{n}{d}) $
意思是这个 (h(n)) 可以用埃筛，那么这个问题到这里就解决了，但是会不会有线筛的做法呢？
这个 (id*varphi) 狄利克雷卷积在这里处理过。
那么来一波线性的做法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1000000;
int prime[MAXN+1];
int &ptop=prime[0];
ll h[MAXN+1];
int pk[MAXN+1];
inline void sieve(){
const int &n=MAXN;
for(int i=2;i<=n;i++){
if(!pk[i]){
ptop++;
prime[ptop]=i;
pk[i]=i;
h[i]=i+i-1;
}
for(int j=1;j<=ptop;j++){
int &p=prime[j];
int t=i*p;
if(t>n)
break;
if(i%p){
pk[t]=pk[p];
h[t]=h[i]*h[p];
}
else{
pk[t]=pk[i]*p;
if(pk[t]==t){
h[t]=(t-i)+h[i]*p;
}else{
h[t]=h[pk[t]]*h[t/pk[t]];
}
break;
}
}
}
for(int i=1;i<=n;i++){
h[i]-=i;
}
for(int i=1;i<=n;i++){
h[i]+=h[i-1];
}
}
inline ll G(int n){
ll res=h[n]-h[1];
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in","r",stdin);
#endif // Yinku
sieve();
int n;
while(~scanf("%d",&n)){
if(n==0)
break;
else{
printf("%lld
",G(n));
}
}
}