2016年9月2日 星期五

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

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

題目概述:
給數字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;
   }
}

沒有留言:

張貼留言