[mathjax]
题目链接:POJ 3090
题意:
在\((0,0)\)为左下角,\((N,N)\)为右上角的矩形中,除了\((0,0)\)之外,每个点上都插着一个钉子,如下图所示.求在\((0,0)\)往四周看,能够看多少个钉子.一个钉子能被看到,当且仅当连接它和原点的线段上没有其他钉子.
Solution:
除了\((1,0),(0,1),(1,1)\)这三个钉子外,一个钉子\((x,y)\)能被看到当且仅当\(gcd(x,y)=1\),即互质.并且观察可以发现,能看到的钉子关于\(y=x\)对称.于是可以只考虑一半,转化为求对于每个\(2<=x<=N\),有多少个y满足\(1<=y<x\)且\(gcd(x,y)=1\),即x的欧拉函数值. 可以通过Eratosthenes筛法求出\([2,y]\)中每个数的欧拉函数,也可以用线性筛法.
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
#define MAX_N 2000000001
typedef long long ll;
typedef unsigned long long ull;
int phi[1005];
void euler(int n){
for(int i=2;i<=n;i++) phi[i]=i;
for(int i=2;i<=n;i++){
if(phi[i]==i){
for(int j=i;j<=n;j+=i){
phi[j]=phi[j]/i*(i-1);
}
}
}
}
int main() {
int T;
cin>>T;
euler(1000);
int kase=0;
while(T--){
int n;
cin>>n;
int ans=3;
for(int i=2;i<=n;i++){
ans+=phi[i]*2;
}
printf("%d %d %d\n",++kase,n,ans);
}
return 0;
}