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).
inputthe 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.
outputin the single line print a single integer — the answer to the problem modulo 1000000007 (109?+?7).
sample test(s)
input41 4 3 2
output15
input26 3
output13
题意：
给你一个a序列，找出一个b序列，1?≤?bi?≤?ai，使得max(bi)=lcm(bi)，问这样的bi序列有多少个。
思路：
先对a排序，枚举i=max(bi)，对i因式分解，那么大于等于i的部分很好处理，直接pow_mod()相减，小于i的部分就任意取一个约束就够了。
代码：
#include #include#include#include#include#include#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;i<=a[n];i++) // 枚举答案 { vectorfac; for(j=1;j*j<=i;j++) // factor { if(i%j==0) { fac.push_back(j); if(j*j!=i) fac.push_back(i/j); } } sort(fac.begin(),fac.end()); int pos,pre=1; res=1; for(j=1;j