标题效果：有一个格子组件图，假设三个人在一条直线上，那么第一个人将不会看到第三人。现在，有一个人站在(1,1)在。我问他是否能看到n*n的人数的矩阵。
思考：如果你想站(1,1)这名男子看到了一个立场(x,y)一个人。gcd(x,y) == 1，这是一个经典的模型，仅仅要求出n以内phi的和就能够了。
方法就是线性筛。
CODE：
#include#include #include #include #define MAX 40010using namespace std;int n;bool not_prime[MAX];int prime[MAX],primes;int phi[MAX];void Eratosthenes();int main(){ cin >> n; n--; Eratosthenes(); int ans = 0; for(int i = 2;i <= n; ++i) ans += phi[i]; cout << (ans << 1) + 3 << endl; return 0;}void Eratosthenes(){ phi[1] = 1; for(int i = 2;i <= n; ++i) { if(!not_prime[i]) prime[++primes] = i,phi[i] = i - 1; for(int j = 1;j <= primes && prime[j] * i <= n; ++j) { not_prime[prime[j] * i] = true; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } }}
版权声明：本文博主原创文章。博客，未经同意不得转载。