<原># UVA 10780 Again Prime? No Time. [质因子分解]【数论】

UVA 10780 Again Prime? No Time. [质因子分解]【数论】

2016年07月02日 16:42:00 Tabris_ 阅读数:293
标签: 数论 UVA-10780 质因子分解

个人分类: 数学


博客爬取于2019-04-18 17:20:28
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51811570

题目链接: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=120197#problem/H


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 file consists of several test cases. The first line in the file 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

————————————————————————-

题目大意 : 就是N!%m^k=0; 给你n和m 求最大的k;

题解 : 其实很简单 就是把N!与M 质因子分解后
Pi表示第i个质数的贡献是多少
像这样
8 = 2^3 ,Pi=3;

N! ~~ Pn1..Pn2..Pn3..Pn4..Pn5..
M ~~ Pm1..Pm2..Pm3..Pm4..Pm5..

然后找出Pni/Pmi 的最小值 就是我们要求的答案了

附本题代码 170ms

—————————————————–

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <set>

using namespace std;

#define LL long long int
#define _LL __int64

LL prime[2000];
LL Is_or[10101];

void Prime()
{
    int  n = 10010 ,k = 0;
    memset(prime,0,sizeof(prime));
    memset(Is_or,1,sizeof(Is_or));

    Is_or[0]=Is_or[1]=0;

    for(int i=2; i<n; i++)
        if(Is_or[i])
        {
            prime[k++]=i;
            for(int j=i+i; j<n; j+=i)
                Is_or[j]=0;
        }
    return ;
}

int  z[10010][1300];

void init()
{
    memset(z,0,sizeof(z));

    int  temp,k;

    for(int i=1; i<10000; i++)
    {
        temp=i;
        k=0;
        while(prime[k]<=temp&&prime[k]!=0)
        {
            while(temp%prime[k]==0)
            {
                temp/=prime[k];
                z[i][k]++;
            }
            k++;
        }
    }

    for(int j=0; j<1300; j++)
    {
        for(int i=2; i<10010; i++)
        {
            z[i][j]+=z[i-1][j];
        }
    }

    return ;
}

int mm[1300];

int solve(int temp)
{
    memset(mm,0,sizeof(mm));

    int k=0;
    while(prime[k]<=temp&&prime[k]!=0)
    {
        while(temp%prime[k]==0)
        {
            temp/=prime[k];
            mm[k]++;
        }
        k++;
    }

    return k;
}


int main()
{
    Prime();
    init();

    int t,p=0;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;

        int sum=10000;

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

        int num=solve(m);

        for(int i=0; i<num; i++)

            if(mm[i])
                sum=min(sum,z[n][i]/mm[i]);

        printf("Case %d:\n",++p);

        if(sum)
            printf("%d\n",sum);
        else
            printf("Impossible to divide\n");
    }
    return 0;
}

 上一篇
<原>#  LightOJ 1090 Trailing Zeroes (II) [分解]【数论】 <原># LightOJ 1090 Trailing Zeroes (II) [分解]【数论】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2016-07-03
下一篇 
<原>#  Light 1045 Digits of Factorial 【数论】 <原># Light 1045 Digits of Factorial 【数论】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2016-06-30
  目录