题目链接：uva 11014 - Make a Crystal

题目大意：给定n，表示在一个三维的空间，在坐标均不大于n的点中选取2个点，保证这两个点与(0,0,0)三点不同线。问能找到多少对。

解题思路：容斥原理，如果有坐标(x,y,z),并且(2x,2y,2z)在范围内，那个该对点就不可取，于是要减掉包含公共因子的部分。所以枚举因子，但是如果因子包含有偶数个质因子，则加上。

#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; const int maxn = 200000; int np, pri[maxn+5], vis[maxn+5]; void priTable (int n) { np = 0; memset(vis, 0, sizeof(vis)); for (int i = 2; i <= n; i++) { if (vis[i]) continue; pri[np++] = i; for (int j = 2*i; j <= n; j += i) vis[j] = 1; } } ll N; inline ll count (ll n) { return n * n * n - 1; } inline ll fcount (ll n) { int ans = 0; for (int i = 0; i < np && pri[i] <= n; i++) { if (n < maxn && !vis[n]) { ans++; break; } if (n%pri[i] == 0) { ans++; n /= pri[i]; if (n%pri[i] == 0) return 0; } } return ans&1 ? -1 : 1; } ll solve () { ll ans = count(N+1); for (ll i = 2; i <= N; i++) { ll t = fcount(i); ans += count(N/(2*i) * 2 + 1) * t; } return ans; } int main () { int cas = 1; priTable(maxn); while (scanf("%lld", &N) == 1 && N) { printf("Crystal %d: %lld\n", cas++, solve()); } return 0; }