TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2856
  • 题目
  • P2856ShadowIterator与啦啦操家长
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    ShadowIterator在学校这么吊,被家长知道了!于是,家长们联合起来准备给ShadowIterator致命一击。
    一个有N个家长对ShadowIterator发动攻击,第i个家长的攻击力xi是一个范围在1到mi之间的整数。
    每个家长学的武功都不是同一门派的,比如说华山派、武当派、少林派、崆硐派、古墓派、苹果派、π派……所以真正有效的攻击力是可能是很小的(当然也可能很大)——等于gcd(x1,x2,...,xN)。
    由于这些家长缺乏合作的理念,完全不懂得配合,所以他们总是在自己的攻击力范围中随机选一个值作为这次进攻的攻击力xi
    ShadowIterator早已被一群家长吓傻了,但是大敌当前怎能束手就擒呢?ShadowIterator想知道这N个家长的有效攻击力的所有可能(共有m1*m2*...*mN种可能值)的总和是多少。由于这个数可能比较大,输出它mod 10007的值。

    输入格式

    第一行一个整数N
    第二行N个整数mi,表示第i个家长的攻击力范围。

    输出格式

    一个整数,所有可能的总和mod 10007的值。

    样例输入

    2
    2 2

    样例输出

    5

    提示

    样例解释:
    两个家长的攻击力可能为(1,1),(1,2),(2,1),(2,2),有效攻击力分别为1,1,1,2,所以有效攻击力总和为5.

    数据范围:
    对于5%的数据,N=1
    对于另外5%的数据,N=2
    对于30%的数据,m1*m2*...*mN<=5*106
    对于100%的数据,1<=N<=1000,1<=mi<=106


    来源  感谢nodgd命题并提供数据