Make a Crystal UVA - 11014 （容斥定理）

題意：給定一個NxNxN的正方體，求出最多能選幾個整數點，使得任意兩點PQ不會使PQO共線。

思路：利用容斥原理，設f(k)為點(x, y, z)三點都為k的倍數的點的個數（要扣掉一個原點O)，那麼所有點就是f(1),之後要去除掉共線的，就是扣掉f(2), f(3), f(5)..f(n)，n為素數.因為這些素數中包含了合數的情況，并且這些點必然與f(1)除去這些點以外的點共線，是以扣掉.但是扣掉後會扣掉一些重複的，比如f(6)在f(3)和f(2)各被扣了一次，是以還要加回來，利用容斥原理，答案為

f(1) - f(一個質因子) + f(兩個質因子)...

是以先預處理一個素數表，枚舉n，去分解因子，判斷個數，奇數為減偶數為加，這樣求出答案

#include <stdio.h>
#include <string.h>

const int N = 200005;
long long n;
long long prime[N];
int pn = 0, vis[N];

long long pow3(long long num) {
    return num * num * num - 1;
}

int count(long long num) {
    int ans = 0;
    for (int i = 0; i < pn && prime[i] <= num; i++) {
    if (!vis[num]) {ans++; break;}
    if (num % prime[i] == 0) {
        ans++;
        num /= prime[i];
        if (num % prime[i] == 0) return -1;
    }
    }
    return ans;
}

long long cal(long long num) {
    int t = count(num);
    if (t == -1) return 0;
    if (t&1) return -pow3((n / 2 / num) * 2 + 1);
    else return pow3((n / 2 / num) * 2 + 1);
}

long long solve() {
    long long ans = pow3(n + 1);
    for (long long i = 2; i <= n; i++)
    ans += cal(i);
    return ans;
}

int main() {
    vis[1] = 1;
    for (long long i = 2; i < N; i++) {
    if (vis[i]) continue;
    prime[pn++] = i;
    for (long long j = i * i; j < N; j += i)
        vis[j] = 1;
    }
    int cas = 0;
    while (~scanf("%lld", &n) && n) {
    printf("Crystal %d: %lld\n", ++cas, solve());    
    }
    return 0;
}      

自己選擇的路，跪着也要走完。朋友們，雖然這個世界日益浮躁起來，隻要能夠為了當時純粹的夢想和感動堅持努力下去，不管其它人怎麼樣，我們也能夠保持自己的本色走下去。