Codeforces 1114C(数论+唯一分解)

题目链接：传送门 解题思路:y1s1，拿到这题我脑袋中只有暴力，观摩了别人的博客，学到了点东西。对于本题，我们可以知道，在b进制后有几个0表示的是这个数是b的几次方的倍数，于是题目便转化为了求n的阶乘最大能被b的几次方整除，从唯一分解定理我们可以知道，我们对n的阶乘和b唯一分解得到:\(b=p1^{a1}\times p2^{a2}\times p3^{a3}……\)\(n!=p1^{b1}\times p2^{b2}\times p3^{b3}……\) 于是问题又转化为了求\(\{\frac{b1}{a1},\frac{b2}{a2}……\}\) 于是我们把b分解质因数，把因数和个数存在数组里，然后对于每个因数都去算a的阶乘里有多少个那个因数，然后除以它在b中的次数，求它可以够组成多少个b，对于每个因数都这么算，然后取最小值。 Code:

#include
using namespace std;
#define ll long long
const int N = 1000005;
ll p[N],k[N],n,b;
int cnt;
ll f(ll x,ll y) {
	return x < y?0:x/y+f(x/y,y);
}

void slove(ll x) {
	memset(p,0,sizeof p);
	memset(k,0,sizeof k);
	cnt = 0;
	for(ll i = 2; i * i  1)
		p[++cnt] = x,k[cnt] = 1;
}

ll work(ll n, ll b) {
	slove(b);
	ll ans = 0x3f3f3f3f3f3f3f3f;
	for(int i = 1;i