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，去分解因子，判断个数，奇数为减偶数为加，这样求出答案

原文地址：https://blog.****.net/accelerator_/article/details/36714109

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

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

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

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

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

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

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