Codeforces Round #157 (Div. 1) C. Little Elephant and LCM (数学、dp)_html/css_WEB-ITnose

WBOY
Freigeben: 2016-06-24 11:54:39
Original
1231 Leute haben es durchsucht

C. Little Elephant and LCM

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The Little Elephant loves the LCM (least common multiple) operation of a non-empty set of positive integers. The result of the LCM operation of k positive integers x1,?x2,?...,?xk is the minimum positive integer that is divisible by each of numbers xi.

Let's assume that there is a sequence of integers b1,?b2,?...,?bn. Let's denote their LCMs as lcm(b1,?b2,?...,?bn) and the maximum of them as max(b1,?b2,?...,?bn). The Little Elephant considers a sequence b good, if lcm(b1,?b2,?...,?bn)?=?max(b1,?b2,?...,?bn).

The Little Elephant has a sequence of integers a1,?a2,?...,?an. Help him find the number of good sequences of integers b1,?b2,?...,?bn, such that for all i (1?≤?i?≤?n) the following condition fulfills: 1?≤?bi?≤?ai. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109?+?7).

Input

The first line contains a single positive integer n (1?≤?n?≤?105) ? the number of integers in the sequence a. The second line contains nspace-separated integers a1,?a2,?...,?an (1?≤?ai?≤?105) ? sequence a.

Output

In the single line print a single integer ? the answer to the problem modulo 1000000007 (109?+?7).

Sample test(s)


input

41 4 3 2
Nach dem Login kopieren

output

15
Nach dem Login kopieren

input

26 3
Nach dem Login kopieren

output

13
Nach dem Login kopieren
题意:
Nach dem Login kopieren
给你一个a序列,找出一个b序列,1?≤?bi?≤?ai,使得max(bi)=lcm(bi),问这样的bi序列有多少个。
Nach dem Login kopieren
思路:
Nach dem Login kopieren
先对a排序,枚举i=max(bi),对i因式分解,那么大于等于i的部分很好处理,直接pow_mod()相减,小于i的部分就任意取一个约束就够了。
Nach dem Login kopieren
代码:
Nach dem Login kopieren
<pre name="code" class="n">#include <iostream>#include<cstring>#include<cstdio>#include<string>#include<vector>#include<algorithm>#define INF 0x3f3f3f3f#define maxn 100005#define mod 1000000007typedef long long ll;using namespace std;int n;int a[maxn];ll pow_mod(ll x,ll n){    ll res = 1;    while(n)    {        if(n&1) res = res * x %mod;        x = x * x %mod;        n >>= 1;    }    return res;}void solve(){    int i,j;    ll ans=0,res;    sort(a+1,a+n+1);    for(i=1;ifac;        for(j=1;j*j</algorithm></vector></string></cstdio></cstring></iostream>
Nach dem Login kopieren
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage