UVA 10061 - How many zero's and how many digits ?

UVA 10061 - How many zero's and how many digits ?

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1002

題目概述:

給數字N,B。求N!在B進位下有多少個後導0與有多少位數。

思路:

待補QQ

AC Code:

//By SCJ

#include<iostream>

#include<cmath>

#include<vector>

//#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000

#define endl '\n'

bool np[800];

vector<int> p;

struct P{

   int x,time;

};

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   for(int i=2;i<800;++i)

   {

       if(!np[i]){

           p.push_back(i);

           for(int j=i*i;j<800;j+=i) np[j]=1;

       }

   }

   int n,b;

   while(cin>>n>>b)

   {

       vector<P> bp;

       int tp=b,t;

       for(int i:p)

       {

           t=0;

           while(tp%i==0) tp/=i,t++;

           if(t) bp.push_back({i,t});

           if(!tp) break;

       }

       int ans1=INF;

       double ans2=0;

       for(P i:bp)

       {

           tp=n;t=0;

           while(tp) t+=tp/i.x,tp/=i.x;

           if(t) ans1=min(ans1,t/i.time);

           else ans1=0;

       }

       for(int i=1;i<=n;++i) ans2+=log(i)/log(b);

       cout<<ans1<<' '<<(int)ans2+1<<endl;

   }

}