题目大意
给出一个 ((a+b) imes (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)) 表示 (sumlimits_{i=1}^{l}[gcd(i,x)=1]).即计算 (1sim 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-lfloorfrac{l}{p_1} floor-lfloorfrac{l}{p_2} floordots+lfloorfrac{l}{p_1p_2} floor+lfloorfrac{l}{p_2p_3} floor+lfloorfrac{l}{p_1p_3} floordots-lfloorfrac{l}{p_1p_2p_3} floor-lfloorfrac{l}{p_1p_2p_4} floor-lfloorfrac{l}{p_1p_3p_4} floordotsdots) 变成了一个简单的容斥,(f(l,x)=) 选 (0) 个数的乘积在 (1sim m) 中的倍数个数 (-) 选 (1) 个数的乘积在 (1sim m) 中的倍数的个数 (+) 选 (2) 个数的乘积在 (1sim 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
%lld
%lld
",1ll*len*l-answer1-answer2,answer1,answer2);
return 0;
}