【欧拉函数||容斥】gcd之和

Description
给出一个数列，求数列中任意一对数的最大公因数之和。
最大公因数的定义可以查看 baike.baidu.com/item/最大公因数 

Input
 多组数据。
输入的第一行包括一个整数表示数据组数T(1<=T<=10)。
每组数据的第一行包括一个整数表示数列的长度N(1<=N<=10000)。
第二行包括N个整数，第i个整数表示数列的第i个数ai(1<=ai<=10000)。

Output
每组数据在单独的一行中输出数列中任意一对数的最大公因数之和。 

Sample Input
3
3
2 1 3
4
4 3 9 6
7
7 7 7 7 7 7 7
Sample Output
3
13
147
HINT
 对于第一组数据:


gcd(2,1)+gcd(2,3)+gcd(1,3)=1+1+1=3

对于第二组数据:

gcd(4,3)+gcd(4,9)+gcd(4,6)+gcd(3,9)+gcd(3,6)+gcd(9,6)=1+1+2+3+3+3=13

对于第三组数据:

gcd(7,7)*(6+5+4+3+2+1)=7*21=147

关于这题有很多种解法。

1.容斥

假设d为N公因数，那么公因数之和就是所有的d乘上 $C$ $2 \choose num(d)$ ，其中num(d)指的是d出现的次数。因为任意两个数才有公约数，从有d这个公因数的所有数中选择两个即可。

然而这下算出来的是所有公因数的和，我们需要的是最大公因数的和。所以要除重，可以利用容斥原理。d算出的答案减去d的倍数算出的答案即为最大公约数之和。例如最大公因数为2的，就可以算出公因数为2的，再减去公因数和为4，8，16...的。倒过来容斥就可以了。

代码见题解 F

2.欧拉函数

首先欧拉函数有个性质： $n = \sum\limits_{d|n}φ(d)$ 也就是说n的所有因数的欧拉函数之和等于n本身。

假设 $gcd(x,y)=n$ ，则x,y小于n的公约数一定是相同的。可以得到：任意两数的gcd等于他们的公因数的欧拉函数值之和。则同样有某个gcd的和为

$n*C$ $2 \choose num(n)$

其中 $2 \choose num(n$ 可以看作是0..num(n)-1的等差求和公式： $0+1+2+..+num(n)-1$ 。n则可以写为 $\sum\limits_{d|n}φ(d)$

$(0+1+2+..+num(n)-1) * \sum\limits_{d|n}φ(d)$

可以看出每个公因数的Φ值乘上自己出现的次数都会对gcd的和做出一定贡献。而且因为每个d都有对应的gcd，所以不存在重复的情况。

那每加入一个数x。可以把答案加上 $num(k) * \sum\limits_{k|x}φ(k)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+233;
ll phi[maxn+23]={0};
ll a[maxn+23];
vector<ll> d[maxn+23];
void phi_t()
{
    for(ll i=2;i<=maxn;i++) phi[i]=0;
    phi[1]=1;
    for(ll i=2;i<=maxn;i++) 
        if(!phi[i])
        {
            for(ll j=i;j<=maxn;j+=i)
            {
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);  
            } 
        }
}
void init()
{
    for(ll i=1;i<=maxn;i++)
    {
        for(ll j=i;j<=maxn;j+=i)
        {
            d[j].push_back(i);
        }
    }   
    phi_t();
}
ll t;
int main()
{
    init();
    scanf("%d",&t);
    for(ll i=1;i<=t;i++)
    {
        ll n;
        ll sum=0;
        ll num[maxn+23];
        memset(num,0,sizeof(num));
        scanf("%lld",&n);
        for(ll j=1;j<=n;j++)
        {
            scanf("%d",&a[j]);
            for(ll k=0;k<d[a[j]].size();k++)
            {
                sum+=phi[d[a[j]][k]]*(num[d[a[j]][k]]++);
            }
        }
        printf("%lld\n",sum);
    }
}

3.莫比乌斯反演

mobius