频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
Again Prime? No Time.(uva10870+数论)
2015-05-15 10:40:49      个评论    来源:寻找&星空の孩子  
收藏   我要投稿

Again Prime? No time.
Input: standard input
Output: standard output
Time Limit: 1 second


The problem statement is very easy. Given a number n you have to determine the largest power of m, not necessarily prime, that pides 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 and n (0. The integers are separated by an space. There will be no invalid cases given and there are not more that500 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 pides n! or a line "Impossible to pide" (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;最大的k;

 

思路:先算M的质因子m,并保存质因子的个数,从N开始递减到N/m,计算每个质因子在N!中出现的次数,取最小。

 

一开始我的思路是取最大的质因子,然后发现错了,然后想是质因子*个数最大的那个,然后想了下40,100就不对了。所以就把所有的质因子都算了一次。(本来以为会超时。。。结果142ms过。o(︶︿︶)o 唉)

 

转载请注明出处:https://blog.csdn.net/u010579068

 

题目连接:https://acm.hust.edu.cn/vjudge/contest/view.action?cid=77956#problem/E

 

 

#include
#include
#define LL long long
LL a[10005];
inline void Maxprime(LL x)
{
    LL t=1,k=0;
    for(LL i=2; i<=x; i++)
    {
        while(x%i==0)
        {
            t=i;
            a[i]++;
            x/=i;
        }
    }
    if(t==1)
    {
        a[x]=1;
    }
}
inline LL Ssum(LL x)
{
    return (x*(x+1))/2;
}
LL Sumprime(LL x,LL mod)
{
    LL t=0;
    while(x)
    {
        if(x%mod==0) t++,x/=mod;
        else return t;
    }
    return 0;
}

int main()
{
    LL n,m,T,caseT=1;
    scanf("%lld",&T);
    while(caseT<=T)
    {
        memset(a,0,sizeof(a));
        scanf("%lld%lld",&m,&n);
        LL mod;
        Maxprime(m);

        LL  sum,minsum=9999999999;
        for(LL j=2; j<=m; j++)
        {

            if(!a[j]) continue;
            sum=0;
            for(LL i=n; i>n/j; i--)
            {
                LL tmp=Sumprime(i,j);
                if(tmp) sum+=Ssum(tmp);
            }
            if(minsum>sum/a[j]) minsum=sum/a[j];
        }
        printf("Case %lld:\n",caseT++);
        if(!sum) printf("Impossible to pide\n");
        else printf("%lld\n",minsum);
    }
    return 0;
}

 

 

 

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 数论
上一篇:一个能将给定非负整数数组中的数字排列成最大数字的函数
下一篇:二维平面曼哈顿距离最小生成树模版
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站