Description：

求： $$ \sum_{i_1|a_1}\sum_{i_2|a_2}\cdots\sum_{i_n|a_n}\varphi(i_1i_2\cdots_n) $$ $1\leqslant n\leqslant10^5,1\leqslant a_i\leqslant10^7$

Solution：

看到 $\begin{align}\sum_{i|a}\end{align}$ 这种形式就有一个重要的方法是把它每个质数拆开来分别考虑，由于欧拉函数是积性的，所以这题也是。

设： $$ a_i=\prod_{j=1}^mp_j^{t_{i,j}} $$

$$ \sum_{i_1|a_1}\sum_{i_2|a_2}\cdots\sum_{i_n|a_n}\varphi(i_1i_2\cdots i_n) $$

$$ =\prod_{i=1}^m(\sum_{i_{1,i}=0}^{t_{1,i}}\sum_{i_{2,i}=0}^{t_{3,i}}\cdots\sum_{i_{n,i}=0}^{t_{n,i}}\varphi(p_i^{\begin{align}\sum_{k=1}^ni_{k,i}\end{align}})) $$

$$ =\prod_{i=1}^m[(\prod_{k=1}^n\sum_{i_{k,i}=0}^{t_{k,i}}p_i^{i_{k,i}}-1)\times\frac{p_i-1}{p_i}+1] $$

所以可以暴力 $O(\sqrt N)$ 分解质因数，再维护一个 $p^i$ 的前缀和，后面那个分式用逆元计算就行。

总之就是质数拆开枚举约数变为枚举质数的指数的那个套路。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

#define MOD 1000000007

int a[MAXN];

int tot = 0;

struct prime

{

	int k,t;

}p[MAXN * 20];

void divide(int k)

{

	int s = k;

	for(int i = 2;i * i <= k;++i)

	{

		if((k % i) == 0)

		{

			int cnt = 0;

			while(s % i == 0)

			{

				++cnt;

				s /= i;

			}

			++tot;p[tot].k = i;p[tot].t = cnt;

		}

	}

	if(s != 1)

	{

		++tot;p[tot].k = s;p[tot].t = 1;

	}

	return;

}

bool cmp_k_t(prime a,prime b){return (a.k == b.k ? a.t > b.t : a.k < b.k);}

typedef long long ll;

ll power[40];

void calc_power(int k)

{

	power[0] = 1;

	for(int i = 1;i <= 31;++i)power[i] = power[i - 1] * k % MOD;

	for(int i = 1;i <= 31;++i)power[i] = (power[i - 1] + power[i]) % MOD;

	return;

}

ll quick_power(ll a,int b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)divide(a[i]);

	sort(p + 1,p + 1 + tot,cmp_k_t);

	ll ans = 1,res = 1;

	for(int i = 1;i <= tot;++i)

	{

		if(i == 1 || p[i].k != p[i - 1].k)calc_power(p[i].k);

		res = (res * power[p[i].t]) % MOD;

		if(i == tot || p[i].k != p[i + 1].k)

		{

			ans = (ans * ((res - 1 + MOD) % MOD * (p[i].k - 1 + MOD) % MOD * quick_power(p[i].k,MOD - 2) % MOD + 1)) % MOD;

			res = 1;

		}

	}

	cout << ans << endl;

	return 0;

}