【题目链接】
http://poj.org/problem?id=3090
【算法】
通过观察发现，在这个平面直角坐标系中，除了(1,1),(1,0)和(0,1)，所有可见点的横纵坐标互质
那么，问题就转化为了求 2 * (phi(1) + phi(2) + ... + phi(n)) + 3
预处理phi的前缀和，O(1)回答询问，即可
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 1010 int i,n,TC,T; int sum[MAXN]; inline void init() { int i,j,tmp,cnt = 0; static int f[MAXN],prime[MAXN],phi[MAXN]; for (i = 2; i < MAXN; i++) { if (!f[i]) { f[i] = prime[++cnt] = i; phi[i] = i - 1; } for (j = 1; j <= cnt; j++) { tmp = i * prime[j]; if (tmp >= MAXN) break; f[tmp] = prime[j]; if (prime[j] == f[i]) { phi[tmp] = phi[i] * prime[j]; break; } else phi[tmp] = phi[i] * (prime[j] - 1); } } for (i = 1; i < MAXN; i++) sum[i] = sum[i-1] + phi[i]; } int main() { init(); scanf("%d",&T); while (T--) { scanf("%d",&n); printf("%d %d %d ",++TC,n,2*sum[n]+3); } return 0; }