题意：给定n个数ai, ai <= 10000, n <= 10000, 从中选出4个数要求gcd为1，这样的集合有多少个？
分析：首先总共集合nCr(n, 4) = n*(n-1)*(n-2)*(n-3)/24个，那么需要减掉gcd >=2 的集合。先减掉gcd为各个素数的方案数目，然后再由这些素数组成一些因子，考虑gcd为这些因子的情况。最后总结起来就是，素数个数为奇数时，减去；素数个数为偶数时，加上。具体实现的时候只要对每个ai分解质因数，然后单独考虑他的素因子能组成哪些数，这样再计算。
#include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x7f7f7f7f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII; const int maxn = + ;
int a[maxn];
LL vis[][maxn], p[], pa[];
int cnt;
void dfs(int st, int pos, int lim) {
if(pos == lim) {
int tmp = ;
for(int i = ; i < pos; i++)
tmp *= pa[i];
vis[lim][tmp]++;
return;
}
for(int i = st; i < cnt; i++) {
pa[pos] = p[i];
dfs(i+, pos+, lim);
}
}
int main() { int n;
while(scanf("%d", &n) == ) {
memset(vis, , sizeof vis);
for(int i = ; i <= n; i++) {
scanf("%d", a+i);
int x = a[i];
cnt = ;
for(int j = ; j*j <= x; j++) {
if(x%j == ) {
p[cnt++] = j;
while(x%j == )
x /= j;
}
}
if(x != )
p[cnt++] = x;
for(int j = ; j <= cnt; j++)
dfs(, , j);
}
double ans = 1.0*n*(n-)*(n-)*(n-)/;
for(int i = ; i < ; i++)
for(int j = ; j <= ; j++)
if(vis[i][j] >= ) {
double tmp = 1.0;
for(LL k = vis[i][j]; k > vis[i][j]-; k--)
tmp = tmp*k;
tmp /= ;
ans += ((i&) ? - : )*tmp;
}
printf("%.0f\n", ans);
}
return ;
}
UPD：这题还可以用扩展欧拉函数做？链接：http://scturtle.is-programmer.com/posts/19402.html
其实是概率角度解释解释欧拉函数，然后拓展一下就可以解这个题了。1/p为包含素因子p的概率。1/p^n为n个数都包含素因子p的概率。
ans = m^n * ∏(1-1/(p^n))