AcWing 201. 可见的点

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 201. 可见的点原题链接简单

作者：

秦淮岸灯火阑珊 , 2019-02-22 17:27:35 , 所有人可见 , 阅读 3567

14

3

原题链接
 更好的阅读体验

题目描述

在一个平面直角坐标系的第一象限内，如果一个点 $(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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

11 评论

ywfwljm 3个月前

$φ$

凉筑 9个月前

这段代码实现了欧拉函数（Euler’s Totient Function）的计算。欧拉函数 ( \phi(n) ) 是一个整数函数，用于计算小于或等于 ( n ) 的正整数中，与 ( n ) 互质的整数个数。具体来说，这段代码使用了一种称为埃拉托斯特尼筛法（Sieve of Eratosthenes）的优化算法来计算每个整数 ( i ) 的欧拉函数值

### 具体解释

初始化 phi 数组：
cpp for(long long i = 2; i <= n; i++) phi[i] = i; // 初始化 phi 数组，使 phi[i] = i
筛法更新 phi 数组：
cpp for(long long i = 2; i <= n; i++) if (phi[i] == i) // 如果 phi[i] 仍然是 i，说明 i 是一个质数 //从质数起手,遍历每个质数的倍数从而遍历[1, n]；
在这个循环中，如果 phi[i] 仍然等于 ( i )，则 ( i ) 是一个质数。质数的特性是除了 1 和它自身之外没有其他因子，所以它们的 phi 值在初始化后没有被改变。
更新 phi 数组中以质数 ( i ) 为因子的元素：
cpp for(long long j = i; j <= n; j += i) phi[j] = phi[j] / i * (i - 1); // 更新 phi[j] 的值
对于每个质数 ( i )，从 ( i ) 开始，以 ( i ) 为步长更新 phi 数组中的所有元素。对于每个这样的 ( j )，phi[j] 的值被更新为 phi[j] / i * (i - 1)。这是因为，如果 ( j ) 是 ( i ) 的倍数，那么 ( j ) 中包含了一个质因子 ( i )，所以我们要用 ( i-1 ) 代替 ( i ) 来更新 phi[j] 的值。

凉筑 9个月前

举例 14
$\phi[14]$ 的值应该是 6。

首先，欧拉函数 $\phi(n)$ 的定义是小于等于 $n$ 的正整数中与 $n$ 互质的整数个数。对于 $n=14$ ，我们需要找到小于 14 且与 14 互质的数，它们是：1、3、5、9、11 和 13，所以 $\phi(14) = 6$ 。

我们逐步分析如何计算 $\phi(14)$ 。

初始化 phi 数组：
cpp for(long long i = 2; i <= n; i++) phi[i] = i;
初始化后，phi 数组如下：
phi[2] = 2 phi[3] = 3 phi[4] = 4 phi[5] = 5 phi[6] = 6 phi[7] = 7 phi[8] = 8 phi[9] = 9 phi[10] = 10 phi[11] = 11 phi[12] = 12 phi[13] = 13 phi[14] = 14
筛法更新 phi 数组：
对于 $i = 2$ ：
cpp for(long long j = 2; j <= n; j += 2) phi[j] = phi[j] / 2 * (2 - 1);
更新后，phi 数组如下：
phi[2] = 1 phi[4] = 2 phi[6] = 3 phi[8] = 4 phi[10] = 5 phi[12] = 6 phi[14] = 7
…………