链接
点击跳转
题解
枚举最小公倍数
x
x
x，乘法原理统计答案，显然这种情况对答案的贡献是一个连乘的式子，这个其实好统计，因为这个连乘式子的每一项都不超过
d
(
x
)
d(x)
d(x)（
d
(
x
)
d(x)
d(x)表示
x
x
x的约数个数），我只要同类合并用一个快速幂搞搞就行了
然后还要减去那些不包含
x
x
x的
复杂度是
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)，其中一个
l
o
g
log
log来自调和级数、另一个来自快速幂
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 1000000007ll
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct EasyMath
{
ll
fastpow(ll a
, ll b
, ll c
)
{
ll
t(a
%c
), ans(1ll);
for(;b
;b
>>=1,t
=t
*t
%c
)if(b
&1)ans
=ans
*t
%c
;
return ans
;
}
}em
;
ll s
[maxn
], n
, ans
, lim
;
vector
<ll
> f
[100010];
int main()
{
ll i
, j
, x
;
n
=read();
rep(i
,n
)
{
s
[x
=read()]++;
lim
=max(x
,lim
);
}
rep(i
,lim
)for(j
=i
;j
<=lim
;j
+=i
)f
[j
].emb(i
);
for(i
=lim
;i
;i
--)s
[i
]+=s
[i
+1];
rep(i
,lim
)
{
ll t
=1, last
;
for(j
=f
[i
].size()-1;~j
;j
--)
{
if(j
==f
[i
].size()-1)
(t
*=em
.fastpow(j
+1,s
[f
[i
][j
]],mod
)-em
.fastpow(j
,s
[f
[i
][j
]],mod
))%=mod
;
else
(t
*=em
.fastpow(j
+1,s
[f
[i
][j
]]-last
,mod
))%=mod
;
last
=s
[f
[i
][j
]];
}
(ans
+=t
)%=mod
;
}
cout
<<(ans
+mod
)%mod
;
return 0;
}
