题目:
给一个n,n的网格,点可以遮挡视线,问从0,0看能看到多少点
题解:
根据对称性,我们可以把网格按y=x为对称轴划分成两半,求一半的就可以了,可以想到的是应该每种斜率只能看到一个点
因为斜率表达式k=y/x,所以直线上的点都满足这个关系,那么显然当gcd(x,y)==1的时候这个点是直线上的第一个点,其他点的坐标一定是这个点的若干倍
所以问题转化成求gcd(x,y)==1的点对个数,即∑phi[i](1<=i<=n)
欧拉函数即可
1 #include<cstdio> 2 using namespace std; 3 int n,t,ans; 4 int oula(int n) 5 { 6 int ans=n,a=n; 7 for(int i=2;i*i<=n;i++) 8 { 9 if(a%i==0) 10 { 11 ans-=ans/i; 12 while(a%i==0) 13 a/=i; 14 } 15 } 16 if(a>1) ans-=ans/a; 17 return ans; 18 } 19 int main() 20 { 21 scanf("%d",&t); 22 for (int i=1;i<=t;i++) 23 { 24 ans=0; 25 scanf("%d",&n); 26 for (int j=1;j<=n;j++) 27 ans+=oula(j); 28 printf("%d %d %d ",i,n,ans*2+1); 29 } 30 return 0; 31 }