题目描述
在一个平面直角坐标系的第一象限内,如果一个点$(x,y)$与原点$(0,0)$的连线中没有通过其他任何点,则称该点在原点处是可见的。
例如,点$(4,2)$就是不可见的,因为它与原点的连线会通过点$(2,1)$。
部分可见点与原点的连线如下图所示:
编写一个程序,计算给定整数N的情况下,满足$0≤x,y≤N$的可见点$(x,y)$的数量(可见点不包括原点)。
输入格式
第一行包含整数C,表示共有C组测试数据。
每组测试数据占一行,包含一个整数N。
输出格式
每组测试数据的输出占据一行。
应包括:测试数据的编号(从1开始),该组测试数据对应的N以及可见点的数量。
同行数据之间用空格隔开。
数据范围
$1≤N,C≤1000$
样例
输入样例:
4
2
4
5
231
输出样例:
1 2 5
2 4 13
3 5 21
4 231 32549
欧拉函数 $O(NlogN)$
分析这道题目,我们发现除了(1,0),(0,1),(1,1)三个钉子,其他钉子被看到,只有满足了$1 \le x,y \le N,x \neq y$ 而且$gcd(x,y)=1$
然后我们再次发现,能够看到的钉子,是沿着$(0,0) (n,n)$这条直线对称的,所以我们只要考虑其中一半就好了,然后最后乘以2即可.
然后满足上述性质的钉子,x的数量恰好就是$\varphi(y)$
有了性质的数学题目是什么,就是直接套公式.$ans=3+2*\sum_{i=2}^N \varphi(i)$ 然后我们就只需要利用类似于素数筛选法一样的东西,筛选欧拉函数即可.
C++ 代码
//SDOI仪仗队,和这道题目极为类似,或者说一模一样,只不过不是多组数据.
#include<bits/stdc++.h>
using namespace std;
const int N=41000;
long long phi[N],n,ans;
void euler(long long n)
{
for(long long i=2; i<=n; i++)
phi[i]=i;
for(long long i=2; i<=n; i++)
if (phi[i]==i)
for(long long j=i; j<=n; j+=i)
phi[j]=phi[j]/i*(i-1);
}
int main()
{
cin>>n;
n--;
euler(n);
for(long long i=2; i<=n; i++)
ans=ans+2*phi[i];
if (n==0)
cout<<0<<endl;
else
cout<<ans+3;
return 0;
}
作者:秦淮岸灯火阑珊
链接:https://www.acwing.com/activity/content/code/content/23446/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这个代码提交无法通过。
醉了秦大佬
牛逼可莱丝
(1,0)和(0,1)是不是应该不算在第一象限内
用线性筛可以做到O(n)
求欧拉函数这代码太厉害了,佩服佩服,大佬