自动搬运

查看原文

来自洛谷，原作者为

	Limit 技不如人

搬运于2025-08-24 22:20:54，当前版本为作者最后更新于2020-08-06 13:41:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给出一个 $(a+b)\times (l-1)$ 的矩形,端点为 $(0,0)$ 和 $(l-1,a+b)$,在 $(-1,0)$ 和 $(-1,a+b)$ 的位置有一个特殊点,问又多少点满足和其中一个特殊点之间的连线不经过其他点,和两个特殊点的连线不经过其他点,以及两个特殊点和它的连线都会经过其他点.

分析

对于两线之后不经过其他点的点对 $(x_1,y_1),(x_2,y_2)$ 必定满足 $\gcd(|x_1-x_2|,|y_1-y_2|)=1$(具体可以看看 P2158 的题解区,这里不作多解释),可以发现 $a+b$ 的范围很小,所以考虑枚举所在的行,对于每一行计算答案.

设 $f(l,x)$ 表示 $\sum\limits_{i=1}^{l}[\gcd(i,x)=1]$.即计算 $1\sim l$ 中与 $x$ 互质的数的个数.

那么对于第 $i$ 行第一个特殊点可以看见的点的个数 $=f(l,i-1)$,第二个特殊点可以看见的点的个数 $=f(l,a+b+1-i)$.

考虑 $f$ 的本质,$f(l,x)$ 的计算可以把 $x$ 拆成 $p_1^{k_1}p_{2}^{k_2}p_{3}^{k_3}\dots$.那么 $f(l,x)=l-\lfloor\frac{l}{p_1}\rfloor-\lfloor\frac{l}{p_2}\rfloor\dots+\lfloor\frac{l}{p_1p_2}\rfloor+\lfloor\frac{l}{p_2p_3}\rfloor+\lfloor\frac{l}{p_1p_3}\rfloor\dots-\lfloor\frac{l}{p_1p_2p_3}\rfloor-\lfloor\frac{l}{p_1p_2p_4}\rfloor-\lfloor\frac{l}{p_1p_3p_4}\rfloor\dots\dots$ 变成了一个简单的容斥,$f(l,x)=$ 选 $0$ 个数的乘积在 $1\sim m$ 中的倍数个数 $-$ 选 $1$ 个数的乘积在 $1\sim m$ 中的倍数的个数 $+$ 选 $2$ 个数的乘积在 $1\sim m$ 中倍数的个数 $\dots$

同时被两个点看到的方案数 $=f(l,(i-1)(a+b+1-i))$(可以理解为需要得到将两个数分解之后所得的质数集合的并集,$(i-1)(a+b+1-i)$ 换成 $\operatorname{lcm}(i-1,a+b+1,i)$ 也是可以的)

恰好只会被第一个特殊点看到的方案数 $=f(l,i-1)-f(l,(i-1)(a+b+1-i))$.第二个特殊点同理.

代码

#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int PRIME[303]={2,3,5,7,11,13,....};//2000 以内的质数表
int a,b,l;
long long answer1,answer2;
long long sum;
int cnt=0;
int num[100];
void DFS(int now=1,int use=0,long long add=1)
{
	if(now==cnt+1)
	{
		sum+=1ll*(use&1?-1:1)*(l/add);//选了偶数个是加上,选了奇数个是减
		return;
	}
	DFS(now+1,use,add);
	DFS(now+1,use+1,add*num[now]);
}
long long Calc(int a)
{
	if(!a)
	{
		return 1;
	}
	sum=0;
	cnt=0;
	REP(i,0,302)//将数分解为若干质数的幂次的乘积的形式
	{
		if(a%PRIME[i]==0)
		{
			num[++cnt]=PRIME[i];
			while(a%PRIME[i]==0)
			{
				a/=PRIME[i];
			}
		}
	}
	if(a^1)
	{
		num[++cnt]=a;
	}
	DFS();//暴力 DFS 容斥
	return sum;
}
int main()
{
	scanf("%d%d%d",&a,&b,&l);
	int len=a+b+1;
	REP(i,1,len)
	{
		a=i-1;
		b=len-i;
		long long ua=Calc(a);//第一个特殊点可以看见的点的数量
		long long ub=Calc(b);//第二个特殊点可以看见的点的数量
		long long uab=Calc(a*b);//第一个和第二个特殊点可以同时看见的点的数量
		answer2+=uab;//记录答案
		answer1+=ua-uab+ub-uab;
	}
	printf("%lld\n%lld\n%lld\n",1ll*len*l-answer1-answer2,answer1,answer2);
	return 0;
}