[ZOJ3435]Ideal Puzzle Bobble

题面戳我

题意:你现在处于\((1,1,1)\),问可以看见多少个第一卦限的整点。

第一卦限:就是\((x,y,z)\)中\(x,y,z\)均为正

sol

首先L--,W--,H--,然后答案就变成了

\[\sum_{i=1}^{L}\sum_{j=1}^{W}\sum_{k=1}^{H}[\gcd(i,j,k)==1]+\sum_{i=1}^{L}\sum_{j=1}^{W}[\gcd(i,j)==1]
\]

\[+\sum_{i=1}^{L}\sum_{j=1}^{H}[\gcd(i,j)==1]+\sum_{i=1}^{W}\sum_{j=1}^{H}[\gcd(i,j)==1]+3
\]

(加三是因为还有\((0,0,1),(0,1,0),(1,0,0)\)三个点)

所以直接做就行了。

第一个式子看上去有三个\(\sum\),但套路还是一样的,可以化成$$\sum_{i=1}^{\min(L,W,H)}\mu(i)\lfloor\frac Li\rfloor\lfloor\frac Wi\rfloor\lfloor\frac Hi\rfloor$$

数论分块走一波

code

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1000000;
int pri[N+5],tot,zhi[N+5],mu[N+5],L,W,H;
void Mobius()
{
zhi[1]=mu[1]=1;
for (int i=2;i<=N;i++)
{
if (!zhi[i]) pri[++tot]=i,mu[i]=-1;
for (int j=1;j<=tot&&i*pri[j]<=N;j++)
{
zhi[i*pri[j]]=1;
if (i%pri[j]) mu[i*pri[j]]=-mu[i];
else break;
}
}
for (int i=1;i<=N;i++) mu[i]+=mu[i-1];
}
ll calc(int n,int m)
{
int i=1;ll res=0;
while (i<=n&&i<=m)
{
int j=min(n/(n/i),m/(m/i));
res+=1ll*(n/i)*(m/i)*(mu[j]-mu[i-1]);
i=j+1;
}
return res;
}
int main()
{
Mobius();
while (scanf("%d %d %d",&L,&W,&H)!=EOF)
{
L--,W--,H--;
ll ans=0;int i=1;
while (i<=L&&i<=W&&i<=H)
{
int j=min(L/(L/i),min(W/(W/i),H/(H/i)));
ans+=1ll*(L/i)*(W/i)*(H/i)*(mu[j]-mu[i-1]);
i=j+1;
}
printf("%lld\n",ans+calc(L,W)+calc(L,H)+calc(W,H)+3);
}
return 0;
}
上一篇:2014 ACM省赛总结


下一篇:如何给自己的app添加分享到有道云笔记这样的功能