【POJ 3904】 Sky Code

【题目链接】

http://poj.org/problem?id=3904

【算法】

问题可以转化为求总的四元组个数 - 公约数不为1的四元组个数

总的四元组个数为C(n,4),公约数不为1的四元组个数可以用容斥原理求

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 10010

typedef long long ll;

ll i,j,n;

ll all,ans;

ll a[MAXN];

ll cnt[MAXN];

vector< ll > num[MAXN];

inline ll C(ll n,ll m)

{

        ll i;

        ll ret = ;

        if (n < m) return ;

        if (m == ) return ;

        for (i = n; i >= n - m + ; i--) ret *= i;

        for (i = ; i <= m; i++) ret /= i;

        return ret;

}

inline void init()

{

        ll i,j,tmp,s;

        bool flag;

        for (i = ; i <= MAXN; i++)

        {

                tmp = i;

                s = ;

                flag = false;

                for (j = ; j <= sqrt(i); j++)

                {

                        if (tmp % j == )

                        {

                                if (tmp % (j * j) == )

                                {

                                        flag = true;

                                        break;

                                }

                                while (tmp % j == )

                                        tmp /= j;

                                s++;

                        }

                }

                if (tmp > ) s++;

                if (!flag) num[s].push_back(i);

        }

}

int main()

{

        init();

        while (scanf("%lld",&n) != EOF)

        {

                all = C(n,);

                ans = ;

                memset(cnt,,sizeof(cnt));

                for (i = ; i <= n; i++) scanf("%lld",&a[i]);

                for (i = ; i <= n; i++)

                {

                        for (j = ; j <= sqrt(a[i]); j++)

                        {

                                if (a[i] % j == )

                                {

                                        cnt[j]++;

                                        if (j * j != a[i]) cnt[a[i]/j]++;

                                }

                        }

                }

                for (i = ; i < MAXN; i++)

                {

                        for (j = ; j < num[i].size(); j++)

                        {

                                if (i & ) ans += C(cnt[num[i][j]],);

                                else ans -= C(cnt[num[i][j]],);

                        }

                }

                printf("%lld\n",all - ans);

        }

        return ;

}