link:http://uva.onlinejudge.org/external/119/11977.html

题意:已知整数n,且n的阶乘在b进制下末尾至少有t个0,现在告诉我们n和t,求最大值b是多少。。

思路:以前我们做过类似的一题,题目是已知n和b,求最后的末尾0有多少个,其实两个大体思想是一样的,

后面一种的方法是对b进行质因数分解,然后对每个因子求出一个相应的个数,取其中最小的那个

这题是已知0的个数,那我们把n内的质因素筛选出来,然后算出每个因子对应的0的个数,满足的就相乘

下面是我的代码:

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
#define mod 10000019
#define LL long long
using namespace std;
int prime[N],isprime[N],cnt;
struct data
{
    int cnt;
    int num;
}p[N];
bool cmp(data a,data b)
{
    return a.cnt>b.cnt;
}
void f()
{
    int i,j;
    memset(p,0,sizeof(p));
    cnt=0;
    memset(prime,0,sizeof(prime));
    prime[0]=prime[1]=1;
    for(i=2;i<N;i++)
    {
        if(!prime[i])
        {
            isprime[cnt++]=i;
            for(j=i+i;j<N;j+=i)
                prime[j]=1;
        }
    }
}
int main()
{
    int T,n,t,cas;
    int s,i,j,tot;
    LL b;
    scanf("%d",&T);
    f();
    for(cas=1;cas<=T;cas++)
    {
        scanf("%d%d",&n,&t);
        i=j=0,b=1;
        while(i<cnt&&isprime[i]<=n)
        {
            s=0,tot=n;
            while(tot)
            {
                s+=tot/isprime[i];
                tot/=isprime[i];
            }
            p[j].cnt=s;
            p[j].num=isprime[i];
            i++,j++;
        }
        sort(p,p+j,cmp);
        for(i=0;i<j;i++)
        {
            if(p[i].cnt<t)
                break;
            while(p[i].cnt>=t)
            {
                p[i].cnt-=t;
                b=b*p[i].num%mod;
            }
        }
        printf("Case %d: ",cas);
        if(i==0||b==1)
            printf("-1\n");
        else
            printf("%lld\n",b);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation