题解 P3911 【最小公倍数之和】

· · 题解

又是我最喜欢的数论题！！

发现100%的数据中A在50000之内，我们就可以用a[i]来记录A==i的数A有多少个。

然后我们就可以推式子了（我的方法有点鬼畜，接下来写一下我刚刚想起的一个简单的方法。）

首先我们设h[i]为是i倍数的A的两两之积，那么我们可以把是i的倍数的A先加到h[i]中最后让h[i]*=h[i]就好了。

然后再设g[i]为gcd==i的两两数之积，那么我们可得：

 h[i]=∑g[j]    (i|j)

所以我们可以反演得：

g[i]=∑μ[j/i]*h[j] (i|j)

我们反演得到g之和，最后的答案就是∑g[i]/i (1<=i<=N),N是所有A中最大的一个。

(我一开始的方式是用所有两数之积再减去gcd不为1的。。。。其实原理都一样)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 50005
ll us[maxn],zs[maxn],t;
bool v[maxn];
ll h[maxn],g[maxn],a[maxn],x,n,N,tot=0;
inline void read(ll&x){
    x=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    for(;isdigit(ch);ch=getchar())  x=x*10+ch-'0';
}
inline void init(){
    us[1]=1;
    for(int i=2;i<=maxn;i++){
        if(!v[i]) zs[++t]=i,us[i]=-1;
        for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){
            v[u]=1;
            if(!(i%zs[j])) break;
            us[u]=-us[i];
        }
    }
}
int main(){
    init();
    read(n);
    for(int i=1;i<=n;i++) read(x),a[x]++,N=max(N,x),tot+=x;
    tot*=tot;
    for(int i=1;i<=N;i++){
      for(int j=i;j<=N;j+=i) if(a[j]) h[i]+=j*a[j];
      h[i]*=h[i];
    }
    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j+=i) g[i]+=us[j/i]*h[j];
        tot-=g[i]-g[i]/i;
    }
    cout<<tot<<endl;
    return 0;
}