网站更改模板 seo,mip网站实例,用电脑建设个人网站 并用手机访问,重庆网站制作权威乐云践新AcWing 201. 可见的点
题意#xff1a; 题解#xff1a;
我们先说结论:坐标(i,j)#xff0c;如果i和j互质#xff0c;说明该坐标为可见 为什么#xff1f; 我们想想什么样的坐标可见#xff0c;什么样的会被挡住。光线是一个直线#xff0c;在同一个直线上的点会被第一…AcWing 201. 可见的点
题意 题解
我们先说结论:坐标(i,j)如果i和j互质说明该坐标为可见 为什么 我们想想什么样的坐标可见什么样的会被挡住。光线是一个直线在同一个直线上的点会被第一个点挡住而所有光都从一个地方出发也就是如果斜率一样后面会被前面的挡住(暂时不考虑斜率不存在的情况)。对于坐标(i,j),斜率为ki/j,如果i和j不互质设gcd(i,j)d那么(i/d)/(j/d)也等于k且(i/d,j/d)要比i,j小前者会挡住后缀这说明了i和j必须互质不然会被更小的i/d和j/d给挡住 我们观察题目给的图形图形是关于斜率为1的直线对称(也很好理解x与y互质那y也与x互质)因此我们只考虑下半部分 根据横坐标我们依次查看横坐标为1时互质的点的数量为1横坐标为2时互质的数量为1…我们要找的是与横坐标互质且小于横坐标的点的数量这不就是欧拉函数吗 所有答案就是横坐标所对应的欧拉函数的和乘2(因为我们只算了一半)加1(别忘了对称轴上还有一个点)
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn5e49;
int prime[maxn],cnt;
bool st[maxn];
int phi[maxn];
void init(int n){phi[1]1;for(int i2;in;i){if(!st[i]){prime[cnt]i;phi[i]i-1;}for(int j0;prime[j]*in;j){st[prime[j]*i]1;if(i%prime[j]0){phi[i*prime[j]]phi[i]*prime[j];break;}phi[i*prime[j]]phi[i]*(prime[j]-1);}}
}
int main()
{init(maxn-1);int n,m;cinm;for(int T1;Tm;T){cinn;int res1;//对角线那个 for(int i1;in;i)resphi[i]*2;coutT n resendl; }return 0;
}
