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.　　至于为什么有这个公式。我也不大懂。求数论大神指教。。

下面就是代码：

  1 /*
  2  * Author:  yzcstc
  3  * Created Time:  2013/10/26 13:55:35
  4  * File Name: hdu4048.cpp
  5  */
  6 #include<iostream>
  7 #include<sstream>
  8 #include<fstream>
  9 #include<vector>
 10 #include<list>
 11 #include<deque>
 12 #include<queue>
 13 #include<stack>
 14 #include<map>
 15 #include<set>
 16 #include<bitset>
 17 #include<algorithm>
 18 #include<cstdio>
 19 #include<cstdlib>
 20 #include<cstring>
 21 #include<cctype>
 22 #include<cmath>
 23 #include<ctime>
 24 #include<utility>
 25 #define M0(x) memset(x, 0, sizeof(x))
 26 #define Inf 0x7fffffff
 27 #define PB push_back
 28 #define SZ(v) ((int)(v).size())
 29 #define maxn 101001
 30 #define maxm 20010
 31 using namespace std;
 32 int n, m, T, M;
 33 int vis[maxm], tot, phi[maxn + 10], flag[maxm], cnt[maxm], mm;
 34 vector<int> fac[maxn];
 35 
 36 void init(){
 37       for (int i = 2; i < maxm; i++) if (!vis[i]) {
 38         flag[i] = 1;
 39         for (int j = i * 2; j < maxm; j += i) {
 40             if (!vis[j]) vis[j] = flag[j] = 1;
 41             else if (flag[j]) flag[j]++;
 42             if (j%(i*i) == 0) flag[j] = 0;
 43         }
 44       }
 45       
 46       for (int i = 1; i < maxm; ++i)
 47          for (int j = 1; j * j <= i; ++j)
 48             if (i % j == 0){
 49                    fac[i].push_back(j);
 50                    if (j * j < i) fac[i].push_back(i / j);  
 51             }
 52 
 53       for (int i = 1; i < maxn; ++i) phi[i] = i;
 54       for (int i = 2; i < maxn; ++i) 
 55         if (phi[i] == i)
 56            for (int j = i; j < maxn; j += i)
 57                phi[j] = phi[j] / i * (i - 1);
 58 }
 59 
 60 long long power(long long a, long long b){
 61      long long ret = 1;
 62      while (b){
 63           if (b & 1) ret = ret * a % M;
 64           a = a * a % M;
 65           b >>= 1;      
 66      }
 67      return ret;
 68 }
 69 
 70 long long cal(int l){
 71      long long ret = power(cnt[1], l);
 72      for (int i = 2; i <= mm; ++i){
 73            if (flag[i] == 0) continue;
 74            if (flag[i] & 1) ret = (ret - power(cnt[i], l)) % M;
 75            else ret = (ret + power(cnt[i], l)) % M;
 76      }
 77      return  ret < 0 ? ret + M : ret;
 78 }
 79 
 80 void solve(){
 81      scanf("%d%d", &m, &n);
 82      M = n * 10007;
 83      long long ans = mm = 0;
 84      M0(cnt);
 85      int x;
 86      for (int i = 1; i <= m; ++i){
 87          scanf("%d", &x);
 88          mm = max(x, mm);
 89          for (int j = 0; j < fac[x].size(); ++j)
 90             cnt[fac[x][j]]++;    
 91      }
 92      for (int i = 1; i * i <= n; ++i)
 93         if (n % i == 0){
 94              ans = (ans + cal(i) * phi[n / i]) % M;
 95              if (i * i < n) ans = (ans + cal(n / i) * phi[i]) % M;    
 96         }
 97      printf("%I64d
", (ans % M + M) % M / n);
 98 }
 99 
100 int main(){
101    // freopen("a.in","r",stdin);
102    // freopen("a.out","w",stdout);
103     init();
104     scanf("%d", &T);
105     while (T--){
106          solve();
107     }
108     //fclose(stdin); fclose(stdout);
109     return 0;
110 }