题目：How many zero's and how many digits ?
思路：求0的，我们先把base分解质因式，然后求num对base各质因式非0的幂的倍数，取最小值。
求位数的，只求取log10,注意一下精度问题
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> using namespace std; #define maxn 810 int vis[maxn]; int prime[maxn]; int cnt[maxn]; int n_prime=0; void Prime() { memset(vis,true,sizeof(vis)); vis[0]=vis[1]=0; for(int i=2;i<maxn;i++) { if(vis[i]) { prime[++n_prime]=i; for(int j=2*i;j<maxn;j+=i) vis[j]=0; } } // cout<<n_prime<<" "<<prime[n_prime]<<endl; } int get(int num,int factor) { int ans=0; int tmp=factor; while(tmp<=num) { ans+=num/tmp; tmp*=factor; } return ans; } int get_zero(int num,int base) { memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n_prime;i++) { if(prime[i]>base) break; if(base%prime[i]==0) { while(base%prime[i]==0) { base/=prime[i]; cnt[i]++; } } } int ans=0xfffffff; for(int i=1;i<=n_prime;i++) { if(cnt[i]) { ans=min(ans,get(num,prime[i])/cnt[i]); } } return ans; } int get_digit(int num,int base) { double ans=0; for(int i=1;i<=num;i++) ans+=log10(i); ans/=log10(base); return floor(ans+1e-9)+1; } int main() { int num,base; Prime(); while(cin>>num>>base) { cout<<get_zero(num,base)<<" "<<get_digit(num,base)<<endl; } return 0; }