首页 > 代码库 > hdu 4196(数论)
hdu 4196(数论)
题意:问小于n的数的乘积能拼成的最大平方数是多少?
思路:给n!做质数分解在除去指数为奇数的那些质数,由于题目中需要模运算所以不能直接除,必须乘上摸逆。
代码如下:
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。