【欧拉函数||容斥】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])