Sum of LCM (lcmsum)

谁践踏了优雅 2021-09-29 07:06 274阅读 0赞

## 题目 ##

【题目描述】

对于 $ A\_1, A\_2, \\ldots, A\_N $ ，求$\\sum\_\{i = 1\}^N \\sum\_\{j = 1\}^N \\mathrm\{lcm\}(A\_i, A\_j)$ 的值。

$ \\mathrm\{lcm\}(a, b) $ 表示 $ a $ 和 $ b $ 的最小公倍数

【输入格式】

第 $ 1 $ 行， $ 1 $ 个整数 $ N $ 。

第 $ 2 $ 行， $ N $ 个整数 $ A\_1, A\_2, \\ldots, A\_N $ 。

【输出格式】

$ 1 $ 个整数，表示所求的值。

【样例输入】

2 3

【样例输出】

【数据范围与提示】

对于 $ 30\\% $ 的数据， $ 1 \\leq N \\leq 1000, 1 \\leq A\_i \\leq 50000 $ ；

对于另外 $ 30\\% $ 的数据， $ 1 \\leq N \\leq 50000, 1 \\leq A\_i \\leq 1000 $ ；

对于 $ 100\\% $ 的数据， $ 1 \\leq N \\leq 50000, 1 \\leq A\_i \\leq 50000 $ 。

## 题解 ##

期中考考得什么都不会了

记 $ f\_i $ 表示被 $ i $ 整除的 $ a\_j $ 除 $ i $ 的和

$ f\_i =  \\sum\_\{i|a\_j\} a\_j $

$ g\_i $ 表示 $ \\sum\_\{j=1\}^\{n\} \\sum\_\{k=1\}^\{n\} lcm(a\_j,a\_k)\[i|gcd(a\_j,a\_k)\] $

$ g\_i=f\_i^2\*i $

但是 $ i $ 不一定为 $ gcd(a\_j,a\_k) $，那么考虑容斥掉 $ gcd(a\_j,a\_k) $ 为 $ i $ 的倍数的值

$ h\_i=g\_i-\\sum\_\{j=2\}^\{i\*j\\leq max\}h\_\{i\*j\}\*j $

则 $ ans=\\sum\_\{i=1\}^\{max\}h\_i $

## 代码 ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define LL long long
     3 #define _(d) while(d(isdigit(ch=getchar())))
     4 using namespace std;
     5 int R(){
     6     int x;bool f=1;char ch;_(!)if(ch=='-')f=0;x=ch^48;
     7     _()x=(x<<3)+(x<<1)+(ch^48);return f?x:-x;}
     8 const int N=1e5+5;
     9 int n,a[N],mx;
    10 LL ans,f[N],g[N];
    11 int main(){
    12     n=R();
    13     for(int i=1;i<=n;i++){
    14         mx=max(a[i]=R(),mx);
    15         for(int j=1;j*j<=a[i];j++)
    16             if(a[i]%j==0){
    17                 g[j]+=a[i]/j;
    18                 if(j*j!=a[i])g[a[i]/j]+=j;
    19             }
    20     }
    21     for(int i=1;i<=mx;i++)f[i]=g[i]*g[i]*i;
    22     for(int i=mx;i;i--){
    23         for(int j=2;i*j<=mx;j++)
    24             f[i]=f[i]-f[i*j]*j;
    25         ans+=f[i];
    26     }
    27     cout<<ans<<endl;
    28     return 0;
    29 }

转载于:https://www.cnblogs.com/chmwt/p/10796798.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/9a688dcc679c492f901fd3abf4aff2a0.png