Codeforces 839D Winter is here【数学:容斥原理】

D. Winter is here

time limit per test:3 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

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 (109 + 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 (109 + 7).

Examples

Input

3
3 3 1

Output

12

Input

4
2 3 4 6

Output

39

Note

In the first sample the clans are {1}, {2}, {1, 2} so the answer will be 1·3 + 1·3 + 2·3 = 12

题目链接:http://codeforces.com/contest/839/problem/D

下面给出AC代码:

 1 #include<cstdio>
 2 const int N=1000010,P=1000000007;
 3 int n,i,j,x,ans,po[N],a[N],f[N];
 4 int main(){
 5   scanf("%d",&n);
 6   for(po[0]=i=1;i<=n;i++)po[i]=2*po[i-1]%P;
 7   while(n--)scanf("%d",&x),a[x]++;
 8   for(i=N-1;i>1;i--){
 9     for(j=i,x=0;j<N;j+=i)x+=a[j];
10     if(x){
11       f[i]=1LL*x*po[x-1]%P;
12       for(j=i+i;j<N;j+=i)f[i]=(f[i]-f[j]+P)%P;
13       ans=(1LL*f[i]*i+ans)%P;
14     }
15   }
16   printf("%d",ans);
17 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang中time包用法--转

time包中包括两类时间:时间点(某一时刻)和时常(某一段时间) 1时间常量(时间格式化) const ( ANSIC = "Mon Jan...

1.6K80
来自专栏小樱的经验随笔

BZOJ 3038: 上帝造题的七分钟2【线段树区间开方问题】

3038: 上帝造题的七分钟2 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 1469  Solved: 63...

27540
来自专栏菩提树下的杨过

java:快速文件分割及合并

文件分割与合并是一个常见需求,比如:上传大文件时,可以先分割成小块,传到服务器后,再进行合并。很多高大上的分布式文件系统(比如:google的GFS、taoba...

56190
来自专栏Ldpe2G的个人博客

Graphviz4S ---- 在Scala中使用DOT语言绘图的开源工具

21660
来自专栏函数式编程语言及工具

Akka(24): Stream:从外部系统控制数据流-control live stream from external system

 在数据流应用的现实场景中常常会遇到与外界系统对接的需求。这些外部系统可能是Actor系统又或者是一些其它类型的系统。与这些外界系统对接的意思是在另一个线程...

241100
来自专栏积累沉淀

初识HtmlParser

1、概念 网页解析,即程序自动分析网页内容、获取信息,从而进一步处理信息。 htmlparser包提供方便、简洁的处理html文件的方法,它将html页面中...

22950
来自专栏菩提树下的杨过

mybatis的物理分页:mybatis-paginator

文件分割与合并是一个常见需求,比如:上传大文件时,可以先分割成小块,传到服务器后,再进行合并。很多高大上的分布式文件系统(比如:google的GFS、taoba...

23190
来自专栏pangguoming

JDBC上关于数据库中多表操作一对多关系和多对多关系的实现方法

我们知道,在设计一个Java bean的时候,要把这些BEAN 的数据存放在数据库中的表结构,然而这些数据库中的表直接又有些特殊的关系,例如员工与部门直接有一对...

87470
来自专栏GreenLeaves

EF 约定介绍

当前环境为EF Code First开发模式中 一、EF默认约定 1、常用约定 (1)、当没有显示指定实体主键的时候,EF会默认将长得最像Id的属性(且类型为G...

226100
来自专栏一个会写诗的程序员的博客

DuplicateFileException: Duplicate files copied in APK META-INF/LICENSEDuplicateFileException: Duplic

10520

扫码关注云+社区

领取腾讯云代金券