Codeforces Round #157 (Div. 1)C（因数分解+二分+组合数）

62 阅读 0 评论 41 点赞

我是靠谱客的博主美满云朵，最近开发中收集的这篇文章主要介绍Codeforces Round #157 (Div. 1)C（因数分解+二分+组合数），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 
    
4
1 4 3 2

      output 
    
15

      input 
    
2
6 3

      output 
    
13

题意：RT

思路：枚举最大值m=max(b1,b2,b3,.....,bn)，然后对于每个m

求出m的所有因子，排序以后为p1,p2,p3,......,pn

然后对于每个pi，pi+1，求出有多少个aj属于[pi,pi+1)，假设个数为xi

则答案为1^x1 * 2^x2 * 3^x3 * ...... * n^xn，注意还要减去1^x1 * 2^x2 * 3^x3 * ...... * （n-1）^xn，因为要保证至少有一个bi=m

复杂度为O(n * sqrt(n) * logn )

#include 
   
   
    
    
#include 
    
    
     
     
#include 
     
     
      
      
#include 
      
      
       
       
#include 
       
       
         #include 
        
          #include 
         
           #include 
           using namespace std; typedef long long ll; const int MOD = (int)1e9+7; const int MAXN = 100005; int a[MAXN]; int stk[MAXN]; int siz[MAXN]; int isprime[MAXN]; int prime[MAXN]; int q[MAXN]; int pos[MAXN]; int dp[MAXN]; int tol; int sz; int top; int add(int x,int y) { x+=y; if(x>=MOD)x-=MOD; return x; } int sub(int x,int y) { x-=y; if(x<0)x+=MOD; return x; } void getprime() { isprime[1]=1;sz=0; for(int i=2;i<=100000;i++){ if(isprime[i]==0){ prime[sz++]=i; for(ll j=(ll)i*i;j<=100000;j+=i) isprime[j]=1; } } } void getdivisors(int x) { top=0; int res=(int)sqrt(x+0.5); for(int i=0;i 
           
             <=res;i++){ int y=prime[i]; if(x%y!=0)continue; stk[top++]=y; int j=0; while(x%y==0){ x/=y; ++j; } siz[top-1]=j; } if(x>1){ stk[top++]=x; siz[top-1]=1; } } int mpow(int x,int n) { int ans=1; int temp=x; while(n){ if(n&1) ans=(ll)ans*temp%MOD; n>>=1; temp=(ll)temp*temp%MOD; } return ans; } void dfs(int cent,int val) { if(cent==top){ q[tol++]=val; return; } dfs(cent+1,val); for(int i=1;i<=siz[cent];i++) dfs(cent+1,val*mpow(stk[cent],i)); } int erfen(int l,int r,int x) { int po=r+1; while(l<=r){ int m=l+r>>1; if(a[m]>=x){ po=m; r=m-1; } else l=m+1; } return po; } int main() { getprime(); int n,mx=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); mx=max(mx,a[i]); } sort(a+1,a+n+1); int ans=0; for(int i=1;i<=mx;i++){ getdivisors(i); tol=0; dfs(0,1); sort(q,q+tol); for(int j=0;j