题目传送门：51nod
我们可以先观察一下这个$f(x)=\sum_{d|x}\mu(d) \cdot d$。
首先它是个积性函数，并且$f(p^k)=1-p \ (k>0)$，这说明函数$f(x)$的值只与$x$的质因数集合有关，与每个质因数的次数无关，然后我们就容易发现$f(gcd(i,j)) \cdot f(lcm(i,j))=f(i) \cdot f(j)$。
于是原式化为
$$ \begin{aligned}\sum_{i=1}^{n} \sum_{j=1}^{n} f(gcd(i,j)) \cdot f(lcm(i,j)) & =\sum_{i=1}^{n} \sum_{j=1}^{n} f(i) \cdot f(j) \\& =(\sum_{i=1}^{n}f(i))^2 \\\end{aligned} $$
那么我们只需求出$f(x)$的前缀和。
设$g(x)=x,h(x)=[x=1]$，容易证明$f \ast g=h$（这里$\ast$指狄利克雷卷积），那么我们可以用杜教筛求解。
#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<algorithm>#include<map>#define ll long long#define mod 1000000007#define Mod1(x) (x>=mod?x-mod:x)#define Mod2(x) (x<0?x+mod:x)inline ll read(){ll x=0; char c=getchar(),f=1;for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';return x*f;}inline void write(ll x){static int buf[20],len; len=0;if(x<0)x=-x,putchar('-');for(;x;x/=10)buf[len++]=x%10;if(!len)putchar('0');else while(len)putchar(buf[--len]+'0');}inline void writeln(ll x){write(x); putchar('\n');}inline void writesp(ll x){write(x); putchar(' ');}const int limit=2000000,inv2=(mod+1)/2;std::map<ll,ll>mp,mark;int p[limit+10],mn[limit+10],f[limit+10],sum[limit+10];ll n,tot;void euler(int n){tot=0; f[1]=1;for(int i=2;i<=n;i++){if(!mn[i])p[++tot]=i,mn[i]=tot,f[i]=Mod2(1-i);for(int j=1;j<=mn[i]&&i*p[j]<=n;j++)mn[i*p[j]]=j,f[i*p[j]]=(j==mn[i]?f[i]:(ll)f[i]*f[p[j]]%mod);}sum[0]=0;for(int i=1;i<=n;i++)sum[i]=Mod1(sum[i-1]+f[i]);}ll solve(ll n){if(n<=limit)return sum[n];if(mark[n])return mp[n];ll sum=n;for(ll i=2,j;i<=n;i=j+1){j=n/(n/i);sum-=solve(n/i)*(((i+j)%mod)*((j-i+1)%mod)%mod*inv2%mod)%mod;sum=Mod2(sum);}mark[n]=1;return mp[n]=sum;}int main(){n=read();euler(limit);mark.clear();mp.clear();ll ans=solve(n);writeln(ans*ans%mod);return 0;}
51nod2026
