AcWing 201. 可見的點(diǎn)

題意：

題解：

我們先說結(jié)論:坐標(biāo)(i,j)，如果i和j互質(zhì)，說明該坐標(biāo)為可見
為什么？
我們想想什么樣的坐標(biāo)可見，什么樣的會(huì)被擋住。光線是一個(gè)直線，在同一個(gè)直線上的點(diǎn)會(huì)被第一個(gè)點(diǎn)擋住，而所有光都從一個(gè)地方出發(fā)，也就是如果斜率一樣，后面會(huì)被前面的擋住(暫時(shí)不考慮斜率不存在的情況)。對(duì)于坐標(biāo)(i,j),斜率為k=i/j,如果i和j不互質(zhì)，設(shè)gcd(i,j)=d，那么(i/d)/(j/d)也等于k，且(i/d,j/d)要比（i,j）小，前者會(huì)擋住后綴，這說明了i和j必須互質(zhì)，不然會(huì)被更小的i/d和j/d給擋住
我們觀察題目給的圖形，圖形是關(guān)于斜率為1的直線對(duì)稱(也很好理解，x與y互質(zhì)，那y也與x互質(zhì))，因此我們只考慮下半部分
根據(jù)橫坐標(biāo)，我們依次查看，橫坐標(biāo)為1時(shí)，互質(zhì)的點(diǎn)的數(shù)量為1，橫坐標(biāo)為2時(shí)，互質(zhì)的數(shù)量為1…我們要找的是與橫坐標(biāo)互質(zhì)，且小于橫坐標(biāo)的點(diǎn)的數(shù)量，這不就是歐拉函數(shù)嗎
所有答案就是橫坐標(biāo)所對(duì)應(yīng)的歐拉函數(shù)的和，乘2(因?yàn)槲覀冎凰懔艘话?，加1(別忘了對(duì)稱軸上還有一個(gè)點(diǎn))

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=5e4+9; int prime[maxn],cnt; bool st[maxn]; int phi[maxn]; void init(int n){phi[1]=1;for(int i=2;i<=n;i++){if(!st[i]){prime[cnt++]=i;phi[i]=i-1;}for(int j=0;prime[j]*i<=n;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;cin>>m;for(int T=1;T<=m;T++){cin>>n;int res=1;//對(duì)角線那個(gè) for(int i=1;i<=n;i++)res+=phi[i]*2;cout<<T<<" "<<n<<" "<<res<<endl; }return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的AcWing 201. 可见的点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。