Gym 101992D The Millennium Prize Problems

description

Did you hear about the Millennium Prize Problems? They are seven problems in mathematics that were stated by the Clay Mathematics Institute on May 24, 2000. A correct solution for any of these problems results in a million dollar prize being awarded by the institute to the discoverer(s).

Soliman, one of the ECPC judges came up with a new mathematics problem and claimed that it should be the eighth Millennium Prize Problem as he is pretty sure no one could solve it. Here’s the problem:

Given an array A of length N (the array can have duplicate values). What is the sum of all least common multiple (LCM) values for every pair of the array? More formally you need to calculate the following:
$\sum _{i=1}^n\sum _{j=1}^{n}LCM(A_i,A_j)$i=1∑n​j=1∑n​LCM(Ai​,Aj​)
Tefa, one of the ECPC judges suggested that we can add it in the problem set to see if someone can come up with a solution, so can you do it?

Input

The first line of the input contains a single integer T the number of test cases, each test case consists of one line containing N+1 space-separated integers, the first integer is the number N the size of the array and the remaining integers are the elements of the array A, where 1≤N≤105 and 1≤Ai≤105.

Output

For each test case output the answer to the problem modulo 109+7.

Example

Input

2
4 2 6 12 15
5 2 3 7 11 12

Output

335
861

分析

好久没做莫比乌斯函数题了，来一发hhh
这题也许算比较经典？
其实就是要枚举值域来求。
记值域上界为 $N$N， $cn{t}_x$cntx​ 为 $x$x 出现的次数

$\sum _{i=1}^n\sum _{j=1}^{n}LCM(A_i,A_j)=\sum _{i=1}^N\sum _{j=1}^{N}LCM(i,j)\ast cn{t}_i\ast cn{t}_j=\sum _{i=1}^N\sum _{j=1}^N\frac{i\ast j}{gcd(i,j)}\ast cn{t}_i\ast cn{t}_j$i=1∑n​j=1∑n​LCM(Ai​,Aj​)=i=1∑N​j=1∑N​LCM(i,j)∗cnti​∗cntj​=i=1∑N​j=1∑N​gcd(i,j)i∗j​∗cnti​∗cntj​
然后枚举 $d=gcd(i,j)$d=gcd(i,j)，然后枚举 $d$d 的倍数，有
$\sum _{i=1}^N\sum _{j=1}^N\frac{i\ast j}{gcd(i,j)}\ast cn{t}_i\ast cn{t}_j=\sum _{d=1}^N\sum _{i=1}^{\lfloor \frac{N}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{N}{d}\rfloor }i\ast j\ast d\ast \left[gcd\right(i,j)==1]\ast cn{t}_i\ast cn{t}_j=\sum _{d=1}^{N}d\sum _{i=1}^{\lfloor \frac{N}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{N}{d}\rfloor }i\ast j\ast cn{t}_{id}\ast cn{t}_{jd}\sum _{x\mid i,x\mid j}\mu \left(x\right)$i=1∑N​j=1∑N​gcd(i,j)i∗j​∗cnti​∗cntj​=d=1∑N​i=1∑⌊dN​⌋​j=1∑⌊dN​⌋​i∗j∗d∗[gcd(i,j)==1]∗cnti​∗cntj​=d=1∑N​di=1∑⌊dN​⌋​j=1∑⌊dN​⌋​i∗j∗cntid​∗cntjd​x∣i,x∣j∑​μ(x)
然后枚举 $x$x，有
$ans=\sum _{d=1}^{N}d\sum _{x=1}^{\lfloor \frac{N}{d}\rfloor }\mu \left(x\right)\sum _{i=1}^{\lfloor \frac{N}{dx}\rfloor }\sum _{j=1}^{\lfloor \frac{N}{dx}\rfloor }i\ast x\ast cn{t}_{idx}\ast j\ast x\ast cn{t}_{jdx}=\sum _{d=1}^{N}d\sum _{x=1}^{\lfloor \frac{N}{d}\rfloor }\mu \left(x\right)\ast x^2(\sum _{i=1}^{\lfloor \frac{N}{dx}\rfloor }i\ast cn{t}_{idx}{)}^2$ans=d=1∑N​dx=1∑⌊dN​⌋​μ(x)i=1∑⌊dxN​⌋​j=1∑⌊dxN​⌋​i∗x∗cntidx​∗j∗x∗cntjdx​=d=1∑N​dx=1∑⌊dN​⌋​μ(x)∗x2(i=1∑⌊dxN​⌋​i∗cntidx​)2

推式子推到这里做法已经出来了。
预处理
$h\left(x\right)=\sum _{i=1}^{\lfloor \frac{N}{x}\rfloor }i\ast cn{t}_{ix}$h(x)=i=1∑⌊xN​⌋​i∗cntix​即可
复杂度是 $O\left(nlogn\right)$O(nlogn)

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
const int mod = 1e9 + 7;
int cnt[N], p[N], mu[N], x[N], g[N], s[N], ret, maxn = N - 5;
LL t, z = 1;
int main(){
	freopen("lcm.in", "r", stdin);
	int i, j, d, n, m, T, tmp, ans;
	mu[1] = 1;
	for(i = 2; i <= maxn; i++){
		if(!x[i]) p[++ret] = x[i] = i, mu[i] = -1;
		for(j = 1; j <= ret; j++){
			t = z * i * p[j];
			if(t > maxn) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
			mu[t] = -mu[i];
		}
	}
	scanf("%d", &T);
	while(T--){
		ans = 0;
		memset(cnt, 0, sizeof(cnt));
		memset(g, 0, sizeof(g));
		memset(s, 0, sizeof(s));
		scanf("%d", &n);
		for(i = 1; i <= n; i++){
			scanf("%d", &j);
			cnt[j]++;
		}
		n = maxn;
		//for(i = 1; i <= n; i++) printf("%d %d=====\n", i, cnt[i]);
		for(i = 1; i <= n; i++){
			for(j = 1; j <= n / i; j++){
				g[i] = (g[i] + z * cnt[i * j] * j % mod) % mod;
			}
			g[i] = z * g[i] * g[i] % mod;
			//printf("%d %d\n", i, g[i]);
		}
		for(d = 1; d <= n; d++){
			tmp = 0;
			for(i = 1; i <= n / d; i++){
				tmp = (tmp + z * i * i % mod * mu[i] * g[(d * i)] % mod) % mod;	
			}
			tmp = (tmp + mod) % mod;
			ans = (ans + z * d * tmp % mod) % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}