仪仗队【数论】

本文主要是介绍仪仗队【数论】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

给出$(n,n)$的矩阵，求从$(1,1)$能看到多少个点。
$Input$

4

$Output$

9

---

思路：

数论。
这道题如果我们不看$(2,2)$，$(2,1)$，$(1,2)$这三个点的话，就会发现，只有当$gcd(x,y)=1$时才能看见。而这道题如果沿着左下角到右上角的正方形对角线切分的话，又会发现左右两半时一样的。而“一半”又表明$x<y$，所以如果要同时满足这两个条件，就只有$\varphi(y)$个。再加上一开始省略的$(2,2)$，$(2,1)$，$(1,2)$，所以，这道题就是要我们求

$$\sum^{n}_{i=2}\varphi(i)+3$$

---

代码：

#include <cstdio>
#include <iostream>
using namespace std;int p[100001],s,n;int main()
{cin>>n;if (n==1) return printf("0")&0;  //特判n--;for (int i=2;i<=n;i++)p[i]=i;  //初始化for (int i=2;i<=n;i++){if (p[i]==i)for (int j=i;j<=n;j+=i)p[j]=p[j]/i*(i-1);  s+=p[i];  //记录能看到的数量} cout<<s*2+3<<endl;return 0;
}

这篇关于仪仗队【数论】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---