链接：http://acm.hdu.edu.cn/showproblem.php?pid=6053
hdu6053 TrickGCD
题目解析：
令sum[k]为k能够出现的个数 eg： Input 3 6 6 9 各个数字出现的情况 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 8 9 ans=f[2]+f[3]+f[5]-f[6] f[2]: sum[2]=3,sum[4]=3,sum[6]=3,sum[8]=1; 2 2 2 4 4 4 6 6 6 8
f[2]=(1^0)*(2^0)*(3^2)*(4^1)///注释1处
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long LL;
const LL mod=1e9+7;
using namespace std;
const LL maxn=1e5+5;
LL num[maxn],sum[maxn];
LL prime[maxn],mu[maxn];
bool check[maxn];
LL quick(LL a,LL b)
{
LL c=1;
while(b)
{
if(b&1)
c=(a*c)%mod;
a=(a*a)%mod;
b>>=1;
}
return c;
}
void Init()
{
memset(check,false,sizeof(check));
LL cnt=0;
for(LL i=2;i<=maxn;i++)
{
if(!check[i])
{
mu[i]=-1;
prime[cnt++]=i;
}
for(LL j=0;j<cnt&&i*prime[j]<=maxn;j++)
{
check[i*prime[j]]=true;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else
mu[i*prime[j]]=-mu[i];
}
}
}
int main()
{
LL t,n,x,minx,maxx,cas=1;
Init();
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
minx=999999,maxx=-1;
memset(num,0,sizeof(num));
memset(sum,0,sizeof(sum));
for(LL i=1;i<=n;i++)
{
scanf("%lld",&x);
num[x]++;
minx=min(x,minx);
maxx=max(x,maxx);
}
for(LL i=maxx;i>=1;i--)
sum[i]+=sum[i+1]+num[i];
LL s,cnt,tt,ans=0;
for(LL i=2;i<=minx;i++)
{
cnt=1;
tt=-mu[i];
for(LL j=i;j<=maxx;j+=i)
{
tt=(tt*quick(cnt++,sum[j]-sum[j+i]))%mod;//注释1
}
ans=(ans+tt+mod)%mod;
}
cout<<"Case #"<<cas++<<": "<<ans<<endl;
}
return 0;
}
