hdu 4196（数论）

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-06-28 15:26
 5  * Filename     : hdu_4196.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int MOD = 1e9+7;
34 const int MAXN = 10000000+1;
35 int prime[MAXN], n;
36 int f[MAXN];
37 
38 void getPrime()
39 {
40     memset(prime,0,sizeof(prime));
41     for(int i = 2;i <= MAXN;i++)
42     {
43         if(!prime[i])prime[++prime[0]] = i;
44         for(int j = 1;j <= prime[0] && prime[j] <= MAXN/i;j++)
45         {
46             prime[prime[j]*i] = 1;
47             if(i % prime[j] == 0)break;
48         }
49     }
50 }
51 
52 ll inv(ll a,ll m)
53 {
54     if(a == 1)return 1;
55     return inv(m%a,m)*(m-m/a)%m;
56 }
57 
58 //求x！中p（素数）因子的个数
59 ll ff(ll x, ll p){
60     ll tp = p, ret = 0;
61     while(tp <= x){
62         ret += (x/tp);
63         tp = tp*p;
64     }
65     return ret;
66 }
67 
68 int main()
69 {
70     freopen("in.txt", "r", stdin);
71 
72     f[0] = 1;
73     for(int i=1; i<=MAXN; i++) 
74         f[i] = (ll)f[i-1] * i % MOD;
75     getPrime();
76     while(scanf("%d", &n)!=EOF && n){
77         ll ans = 1;
78         for(int i=1; i <= prime[0] && prime[i]<=n; i++){
79             ll tp = ff(n, prime[i]);
80             if(tp & 1) ans = (ll)ans * prime[i] % MOD;
81         }
82         ans = (f[n] * inv(ans, MOD))%MOD;
83         printf("%I64d\n", ans);
84     }
85     return 0;
86 }