Part1:传送门&吐槽

水题..

然而由于线筛里面的\(j\)打成了\(i\)然后就不能1A了OvO

Part2:题目分析

这个正方形是对称的...

而且很显然对角线上只有一个点会被看到...

所以我们只需要考虑对角线下面的一半(标红的)..

(其实你想考虑上面一半也无所谓→→

显然,对于点\((i,j)\)如果\(gcd(i,j)\neq1\),那么一定会被\((\frac{i}{gcd(i,j)},\frac{j}{gcd(i,j)})\)挡住...

所以我们要找第\(i\)列中,\(gcd(i,j)=1\)的\(j\)的个数..

也就是\(\sum_{i=2}^{n}\sum_{j=1}^{i-1}gcd(i,j)=1\)

而很明显这就是欧拉函数的定义...

也就是说这个题让求的不过是\(\sum_{i=2}^{n}\varphi(i-1)\)

而欧拉函数是个积性函数, 可以被线筛出来..

线筛的原理啊证明啊什么的baidu一下就有很多啦(其实是因为我不会啊→→

所以也就做完了..

Part3:代码

由于是水题我都懒得压行了(喜闻乐见)(水题你1A也行啊

#include 
    
     const int N=40404;int prime[N],tot,phi[N];bool notp[N];void euler(int n){    phi[1]=1; notp[1]=1;    for(int i=2;i<=n;++i){        if(!notp[i]) prime[++tot]=i,phi[i]=i-1;        for(int j=1;j<=tot&&i*prime[j]<=n;++j){ //就这个地方我写成++i了            notp[i*prime[j]]=1;            if(i%prime[j]==0){                phi[i*prime[j]]=phi[i]*prime[j];                break;            }else phi[i*prime[j]]=phi[i]*(prime[j]-1);        }    }}int main(){    int n,ans=1; scanf("%d",&n); euler(n);    for(int i=1;i
    

Part4:好像没什么可注意的事项...

• 好像有一条..\(\varphi(1)=1\)
• 好像还有一条.. 我们只考虑了一半,所以记得\(*2\)
• 怎么还有一条.. 别忘了对角线上那个点哦~
• 这次应该是真没了.. 完结撒花吧..