题意

给你一个数组$A$，问有多少个不同的数组$B$满足下列条件：

$1 \le B_i \le A_i $
对于任意的$l,r(1 \le l \le r \le n), gcd(b_l,b_{l+1} \cdots b_r )\ge 2 $

答案对$10^9+7$取模。

思路

由条件2可以得到满足条件的$B$就是使整个$B$的$gcd$不等于$1$.
那么我们枚举每个$gcd$，当前$gcd$对答案的贡献为$\prod_{i=1}^n \frac{a_i}{gcd}$。
然而直接做是$O(n^2)$的，我们考虑枚举贡献值。
用$cnt[i]$表示在$A$中为$[1,i]$的数的出现次数和。这样我们就能在$O(1)$的时间内求出任意的$[l,r]$区间的出现次数和。于是便可以在$O(\log^2 n)$的时间内求出每个$gcd$值的贡献值 因为快速幂还有一个$\log n$,所以是$O(\log^2 n)$ 。
然而，直接这么算是会有重复的。比如$gcd=6$的贡献值中会被$gcd=2$和$gcd=3$的贡献值都算一遍。所以需要容斥一下，或者用线性筛求出莫比乌斯反演函数值。
这里我们选择用线性筛来做。总时间复杂度$O(n\log^2 n)$。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>

//#define test
#define OJ

using namespace std;
const int Nmax=1e5+1;
#ifdef test
typedef long long ll;
#endif
#ifdef OJ
typedef __int64 ll;
#endif
const ll mod=1000000007LL;
const int INF=1e9;
int n;
int a[Nmax];
int Min=INF;

int prime[Nmax];
int is_prime[Nmax];
int prime_cnt;
ll cnt[Nmax];
int mu[Nmax];
inline void get()
{
    for(int i=2;i<Nmax;i++)
        is_prime[i]=1;
    for(long long i=2;i<Nmax;i++)
    {
        if(is_prime[i])
        {
            prime[++prime_cnt]=i;
            mu[i]=1;
        }
        for(int j=1;j<=prime_cnt;j++)
        {
            if(i*prime[j]>=Nmax)
                break;
            is_prime[i*prime[j]]=0;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
}
inline ll sq(ll n)
{
    ll t=n*n%mod;
    if(t<0)
        t+=mod;
    return t;
}
ll qmod(ll base,ll n)
{
    ll ans=1LL;
    base=base%mod;
    while(n)
    {
        if(n&1LL)
            ans=(ans*base)%mod;
        base=base*base%mod;
        n>>=1;
    }
    while(ans<0)
        ans+=mod;
    return ans;
}

int main()
{
    #ifdef test
    //freopen("a.in","r",stdin);
    #endif
    scanf("%d",&n);
    get();
    int ttt=0;
    while(scanf("%d",&n)==1)
    {
        ttt++;
        Min=INF;
        ll ans=0LL;
        ll tmp_ans;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<Nmax;i++)
            cnt[i]=0LL;
        for(int i=1;i<=n;i++)
            cnt[a[i]]++;
        for(int i=2;i<Nmax;i++)
            cnt[i]+=cnt[i-1];
        for(int i=2;i<Nmax;i++)
        {
            if(!mu[i])
                continue;
            tmp_ans=1LL;
            for(int j=1;i*(j-1)<Nmax;j++)
            {
                tmp_ans*=qmod(j-1LL,1LL*(cnt[min(Nmax-1,i*j-1)]-cnt[max(0,i*(j-1)-1)]));
                tmp_ans%=mod;
            }
            tmp_ans%=mod;
            tmp_ans=mu[i]*tmp_ans%mod; 
            ans=(ans+tmp_ans)%mod;
        }
        if(ans<0)
            ans+=mod;

#ifdef test
        printf("Case #%d: %lld\n",ttt,ans);
#endif
#ifdef OJ
        printf("Case #%d: %I64d\n",ttt,ans);
#endif
    }
    return 0;
}