hdu4048

题意：给定m个数，还有n，n表示有一个长度为n的环，现在要求从M个数中选出若干个数，要求选出的数最大公约数为1，填充在n个位置中，选出的数可以重复，求多少种种方案。旋转当成一样的 。

思路：假设现在选出k个数，满足这k个数gcd为1，那么就是一个k种颜色给长度为n的环染色的问题，也就是经典的polya问题。

接着我们考虑如何使其gcd为1。。我们可以考虑下容斥原理。gcd为1统计一遍，然后减掉gcd为2和3的，gcd为6多减了再加回来，依次类推。大体就是这样。。

值得注意的时，答案要mod 10007，当 n为10007的时候无乘法逆元，就会出问题。所以做的时候要mod （10007 * n），最后答案再 / n.　　至于为什么有这个公式。我也不大懂。求数论大神指教。。

下面就是代码：

 /*

  * Author:  yzcstc

  * Created Time:  2013/10/26 13:55:35

  * File Name: hdu4048.cpp

  */

 #include<iostream>

 #include<sstream>

 #include<fstream>

 #include<vector>

 #include<list>

 #include<deque>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<bitset>

 #include<algorithm>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cctype>

 #include<cmath>

 #include<ctime>

 #include<utility>

 #define M0(x) memset(x, 0, sizeof(x))

 #define Inf 0x7fffffff

 #define PB push_back

 #define SZ(v) ((int)(v).size())

 #define maxn 101001

 #define maxm 20010

 using namespace std;

 int n, m, T, M;

 int vis[maxm], tot, phi[maxn + ], flag[maxm], cnt[maxm], mm;

 vector<int> fac[maxn];

 void init(){

       for (int i = ; i < maxm; i++) if (!vis[i]) {

         flag[i] = ;

         for (int j = i * ; j < maxm; j += i) {

             if (!vis[j]) vis[j] = flag[j] = ;

             else if (flag[j]) flag[j]++;

             if (j%(i*i) == ) flag[j] = ;

         }

       }

       for (int i = ; i < maxm; ++i)

          for (int j = ; j * j <= i; ++j)

             if (i % j == ){

                    fac[i].push_back(j);

                    if (j * j < i) fac[i].push_back(i / j);

             }

       for (int i = ; i < maxn; ++i) phi[i] = i;

       for (int i = ; i < maxn; ++i)

         if (phi[i] == i)

            for (int j = i; j < maxn; j += i)

                phi[j] = phi[j] / i * (i - );

 }

 long long power(long long a, long long b){

      long long ret = ;

      while (b){

           if (b & ) ret = ret * a % M;

           a = a * a % M;

           b >>= ;

      }

      return ret;

 }

 long long cal(int l){

      long long ret = power(cnt[], l);

      for (int i = ; i <= mm; ++i){

            if (flag[i] == ) continue;

            if (flag[i] & ) ret = (ret - power(cnt[i], l)) % M;

            else ret = (ret + power(cnt[i], l)) % M;

      }

      return  ret <  ? ret + M : ret;

 }

 void solve(){

      scanf("%d%d", &m, &n);

      M = n * ;

      long long ans = mm = ;

      M0(cnt);

      int x;

      for (int i = ; i <= m; ++i){

          scanf("%d", &x);

          mm = max(x, mm);

          for (int j = ; j < fac[x].size(); ++j)

             cnt[fac[x][j]]++;

      }

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

         if (n % i == ){

              ans = (ans + cal(i) * phi[n / i]) % M;

              if (i * i < n) ans = (ans + cal(n / i) * phi[i]) % M;

         }

      printf("%I64d\n", (ans % M + M) % M / n);

 }

 int main(){

    // freopen("a.in","r",stdin);

    // freopen("a.out","w",stdout);

     init();

     scanf("%d", &T);

     while (T--){

          solve();

     }

     //fclose(stdin); fclose(stdout);

     return ;

 }