题目大意:
给你一个数组 A ,问你有多少不大于 A 的数组 B 使得 B 中所有元素的最大公因数不为1。(数组 B 不大于数组 A 就等价于,对于任意 A 数组中的元素 a [ i ] 和 B 数组中对应元素 b [ i ] ,均有:a [ i ] >= b [ i ])
思路:
容斥思想:该问题就可以转化成求有多少数组 B 满足:B 中的所有元素的最大公因数为 1。
莫比乌斯反演:
设:
那么显然:
那么根据莫比乌斯反演公式可知:
那么我们最后要求的是
分块前缀和技巧:
显然可知:
但是我们如果朴素的方法求每一个
那么我们想办法再继续优化一下上式:
ps:这里的sum(i)表示的是: A 数组中有多少数除 x 向下取整为 i 。
那么现在我们设:
下面给出
ps:
如此可将时间复杂度降为:
代码:
#include<bits/stdc++.h>
using namespace std;
#define maxn 100500
#define MOD 1000000007
#define mod(x) ((x)%MOD+MOD)%MOD
long long int a[maxn],mu[maxn],num[maxn];
int cas=1,n,m,vis[maxn],prime[maxn];
void init_mu()
{
memset(vis,0,sizeof(vis));
mu[1] = 1;
int cnt = 0;
for(int i=2; i<maxn; i++)
{
if(!vis[i])
{
prime[cnt++] = i;
mu[i] = -1;
}
for(int j=0; j<cnt&&i*prime[j]<maxn; j++)
{
vis[i*prime[j]] = 1;
if(i%prime[j]) mu[i*prime[j]] = -mu[i];
else
{
mu[i*prime[j]] = 0;
break;
}
}
}
}
long long int fast_pow(long long int s,long long int x)
{
long long int ans=1;
while(x>0)
{
if(x&1)
{
ans*=s;
ans=mod(ans);
}
x>>=1;
s*=s;
s=mod(s);
}
return mod(ans);
}
long long int F(int x)
{
long long int ans=1;
for(int i=0;i<=maxn/x;i++)
{
ans*=fast_pow((long long int)i,num[min(x*(i+1),maxn)-1]-num[min(x*i,maxn)-1]);
ans=mod(ans);
}
return mod(ans);
}
int main()
{
int T;
scanf("%d",&T);
init_mu();
while(T--)
{
m=maxn<<1;
scanf("%d",&n);
memset(num,0,sizeof(num));
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
num[a[i]]++;
if(a[i]<m)m=a[i];
}
for(int i=1;i<maxn;i++)
{
num[i]+=num[i-1];
}
long long int ans=0;
for(int i=2;i<=m;i++)
{
if(mu[i]==0)continue;
if(mu[i]==1)ans-=F(i);
else ans+=F(i);
ans=mod(ans);
}
ans=mod(ans);
printf("Case #%d: %lld\n",cas++,mod(ans));
}
}