SAC E#1 一道中檔題 Factorial
思路:一個數x在y進制下末尾有多少零, 就是在十進制下能被y連續整除的次數
首先分解k進制,然後對于每個質因數,求出n!裡有多少個質因數,然後如果k裡有x個這個質因數,則求出的結果除以x。最後的答案為這些結果的最小值
如何求n!裡有多少個k分解出來的質因數
代碼QAQ
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const ll sz = 1e7, inf = 1e18;
ll n, k, cnt = 0, num = 0, ans = inf;
ll pri[sz], jz[sz], book[sz];
bool pd[sz];
void getlist() {//沒問題
ll up = min(max(n, k), sz);
pd[1] = pd[0] = 1;
for(ll i = 2; i <= up; i++) {
if(!pd[i]) pri[++cnt] = i;
for(ll j = 1; j <= cnt && pri[j] * i <= up; j++) {
pd[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
void resolvek(ll x) {//沒問題
for(ll i = 1; i <= cnt; i++) {
if(x == 1 || pri[i] > n) break;
if(x % pri[i] == 0) {
jz[++num] = pri[i];
while(x % pri[i] == 0) { //這裡參考的題解!tql!!!
x /= pri[i];
book[num]++;
}
}
}
}
int main() {
scanf("%lld%lld", &n, &k);
getlist();
resolvek(k);
for(ll i = 1; i <= num; i++) {
ll t = n, sum = 0;
while(t) {
t /= jz[i];
sum += t;
}
ans = min(ans, (ll)sum/book[i]);
}
// if(ans == inf) printf("0");
printf("%lld", ans);
return 0;
}
inf 要定義的大一點 剛開始inf = 1<<30 ans 比inf要大, 這就十分gg了
轉載于:https://www.cnblogs.com/Hwjia/p/9888277.html