题面戳我

题意：你现在处于$(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;

}

巴特西

[ZOJ3435]Ideal Puzzle Bobble

sol

code

最新文章

热门文章