Codeforces 839 D. Winter is here （莫比乌斯反演）

Codeforces 839 D. Winter is here （莫比乌斯反演）

Description

Winter is here at the North and the White Walkers are close. John Snow has an army consisting of n soldiers. While the rest of the world is fighting for the Iron Throne, he is going to get ready for the attack of the White Walkers.He has created a method to know how strong his army is. Let the i-th soldier’s strength be ai. For some k he calls i1, i2, …, ik a clan if i1 < i2 < i3 < … < ik and gcd(ai1, ai2, …, aik) > 1 . He calls the strength of that clan k·gcd(ai1, ai2, …, aik). Then he defines the strength of his army by the sum of strengths of all possible clans.Your task is to find the strength of his army. As the number may be very large, you have to print it modulo 1000000007 (10^9 + 7).Greatest common divisor (gcd) of a sequence of integers is the maximum possible integer so that each element of the sequence is divisible by it.

Input

The first line contains integer n (1 ≤ n ≤ 200000) — the size of the army.The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 1000000) — denoting the strengths of his soldiers.

Output

Print one integer — the strength of John Snow’s army modulo 1000000007 (10^9 + 7).

Example input

42 3 4 6

Example output

39

题意

给出一个序列，求其中所有 gcd

思路

题意转化为公式即 ∑k×gcd(a1,a2,...,ak) （其中 gcd

等价于 ∑maxd=2d×∑k×[gcd(a1,a2,...,ak)=d]

我们设 f(x)=∑k×[gcd(a1,a2,...,ak)=x]

设 F(x)=∑x|df(d) ，它也代表我们从整个数列所有 x 的倍数中挑选 k 个组成的情况，因此我们设 v 为数列中 x 倍数的个数，则结果为 1×C1v+2×C2v+...+v×Cvv ，即 v×2v−1

反演以后得到 f(x)=∑x|dμ(dx)F(d) ，最终结果 ans=∑maxd=2d×f(d)

考虑枚举每一个 gcd ，找出序列中所有包含该因子的数有 Vgcd 个，则此时该数对结果的贡献为 Vgcd×2Vgcd−1−S ，其中 S

最终结果 ans=∑maxd=2d×(Vd×2Vd−1−S)

AC 代码

#includeusing namespace std;typedef long long LL;const int mod = 1e9+7;const int maxn = 1e6+10;LL sk[maxn],b[maxn],z[maxn];void solve(){ LL ans=0; for (int i=2; i<=maxn; i++) { LL v=0; for (int j=i; j<=maxn; j+=i) v+=sk[j]; if (!v) continue; ans += (v * z[i]) % mod * b[v-1] % mod; } cout << (ans+mod)%mod << endl;}void init(){ b[0]=1; for (int i=1; i<=maxn; i++) b[i]=b[i-1]*2%mod,z[i]=i; for (int i=2; i<=maxn; i++) for (int j=i+i; j<=maxn; j+=i) z[j]-= z[i];}int main(){ init(); ios::sync_with_stdio(false); int n; while(cin>>n) { memset(sk,0,sizeof(sk)); for (int i=1,x; i<=n; i++) { cin>>x; sk[x]++; } solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。