首页 > 其他 > 详细

UVA 10780 Again Prime? No Time. 分解质因子

时间:2015-12-26 18:40:01      阅读:130      评论:0      收藏:0      [点我收藏+]

The problem statement is very easy. Given a number n you have to determine the largest power of m,
not necessarily prime, that divides n!.
Input
The input ?le consists of several test cases. The ?rst line in the ?le is the number of cases to handle.
The following lines are the cases each of which contains two integers m (1 < m < 5000) and n
(0 < n < 10000). The integers are separated by an space. There will be no invalid cases given and
there are not more that 500 test cases.
Output
For each case in the input, print the case number and result in separate lines. The result is either an
integer if m divides n! or a line ‘Impossible to divide’ (without the quotes). Check the sample input
and output format.
Sample Input
2
2 10
2 100
Sample Output
Case 1:
8
Case 2:
97

 

题意:给定m和n,计算n!中有多少个因子m。

题解:先将m分解质因子,再将1-n分解质因子就好了

技术分享
//meek///#include<bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<bitset>
#include<vector>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define fi first
#define se second
#define MP make_pair
typedef long long ll;

const int N = 10005;
const int M = 1000001;
const int inf = 0x3f3f3f3f;
const int MOD = 1000000007;
const double eps = 0.000001;

vector<int > G;
int H[N],n,m,cnt[N];
int init() {
    for(int i=2;i<=n;i++) {
            int tmp = i;
           for(int j=2;j*j<=tmp;j++) {
               // if(tmp%j==0)
             while(tmp%j==0) tmp/=j,H[j]++;
           }
           if(tmp!=0) H[tmp] ++;
    }
    int ans = inf;
    for(int i=0;i<G.size();i++) ans=min(ans,H[G[i]]/cnt[G[i]]);
    return ans;
}
int main() {
    int T,cas=1;
    scanf("%d",&T);
    while(T--) {
        G.clear();mem(H);mem(cnt);
        scanf("%d%d",&m,&n);
        for(int i=2;i*i<=m;i++) {
            if(m%i==0) G.pb(i);
            while(m%i==0) m/=i,cnt[i]++;
        }
        if(m!=1) G.pb(m),cnt[m]++;
        printf("Case %d:\n",cas++);
        int ans = init();
        if(ans == 0|| ans == inf) printf("Impossible to divide\n");
        else
        printf("%d\n",ans);
    }
    return 0;
}
代码

 

UVA 10780 Again Prime? No Time. 分解质因子

原文:http://www.cnblogs.com/zxhl/p/5078487.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!