洛谷3927 一道中档题

Posted by yjjr's blog on February 6, 2018

标签:数学,模拟

题目描述

SOL君很喜欢阶乘。而SOL菌很喜欢研究进制。

这一天,SOL君跟SOL菌炫技,随口算出了n的阶乘。

SOL菌表示不服,立刻就要算这个数在k进制表示下末尾0的个数。

但是SOL菌太菜了于是请你帮忙。

输入输出格式

输入格式:

每组输入仅包含一行:两个整数n,k。

输出格式:

输出一个整数:n!在k进制下后缀0的个数。

输入输出样例

输入样例#1: 复制

10 40

输出样例#1: 复制

2

说明

对于20%的数据,n <=1000000, k = 10

对于另外20%的数据,n <=20, k <= 36

对于100%的数据,n <=10^12,k <= 10^12

update

1.一组数据

2.K不会==1

3.现在std没有爆long long

4.对数据有问题联系icy (建议大家不要面向数据编程)

 

分析:小学奥数应该都学过短除法……,这题N!%k的余数就是N!在k进制下表示的数

所以转化为判断N!能够整除几次k

可以将k质因数分解,然后再比对N!分解该质因数的个数,选择比值最小的一个作为ans

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
    LL f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
LL n,k,ans=1e19;
void prime(LL x,LL k){
    LL tmp=0;
    for(LL i=x;i<=n;i*=x)tmp+=n/i;
    ans=min(ans,tmp/k);
}
void work(LL x){
    rep(i,2,sqrt(x))
        if(x%i==0){
            LL q=0;
            while(x%i==0){
                q++;
                x/=i;
            }
            prime(i,q);
        }
    if(x!=1)prime(x,1);
}
int main()
{
    n=read(),k=read();
    work(k);
    cout<<ans<<endl;
    return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr