2011-0025
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题目大意是给定一个k进制的数s,以字符串（包含0-9，A-Z，a-z,0<...<9<A<...<Z<a<...<Z）形式表示，求s！（同样表达成k进制）的末尾0的个数。[[BR]]
解法： 对k分解质因数，设k=p1^a1^*p2^a2^...*pm^am^, 然后计算(s!)=p1^b1^*p2^b2^*...*pm^bm^*...[[BR]]
ans=min(b1/a1,...,bm/am)[[BR]]
{{{
#include<iostream>
#include<string>
#include<cassert>
#include<algorithm>
//#include<ctime>
#include<cstring>
#include<cmath>
using namespace std;
//0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
long long powk[63][64]; //2=<k<=62;
int map[128];
int factork[63][63][2];
int prime[18]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};// num is 18
void init()
{
int k,i;
for(k=2;k<=62;k++)
{
powk[k][0]=1;
for(i=1;i<=63;i++)
{
powk[k][i]=powk[k][i-1]*k;
}
}
for(i=0;i<=9;i++)
{
map['0'+i]=i;
}
for(i=0;i<=25;i++)
{
map['A'+i]=10+i;
}
for(i=0;i<=25;i++)
{
map['a'+i]=36+i;
}
for(k=2;k<=62;k++)
{
int tem=k;
int index=1;
for(i=0;i<18;i++)
{
int order=0;
while(tem%prime[i]==0)
{
order++;
tem/=prime[i];
if(tem%prime[i]!=0)
{
factork[k][index][0]=prime[i];
factork[k][index][1]=order;
index++;
}
}
}
factork[k][0][0]=index-1;// the number of k's factorization.
}
}
int main()
{
//time_t _start=clock();
//freopen("input_new","r",stdin);
//freopen("output_new","w",stdout);
init();
char s[100];
int k;
while(scanf("%s %d",s,&k)!=EOF)
{
//printf("%s\n",s);
//cout<<sizeof(s)<<endl;
assert(k<=62&&k>=2);
long long s2dec=0;
for(int i=0;i<strlen(s);i++)
{
s2dec+=map[s[i]]*powk[k][strlen(s)-i-1];
}
assert(log(s2dec*1.0)/log(2.0)<63);
int order[10];
long long num_up=0,num_down=1;
for(int i=1;i<=factork[k][0][0];i++)
{
long long tem=s2dec;
long long ans=0;
while(tem)
{
tem/=factork[k][i][0];
ans+=tem;
}
order[i]=ans;
if(i==1)
{
num_up=ans;
num_down=factork[k][i][1];
}
else if(ans/factork[k][i][1]<num_up/num_down)
{
num_up=ans;
num_down=factork[k][i][1];
}
}
long long output=num_up/num_down;
printf("%lld\n",output);
}
//time_t _end=clock();
//cout<<_end-_start<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}
}}}
by quietsmile题目大意是给定一个k进制的数s,以字符串（包含0-9，A-Z，a-z,0<...<9
解法： 对k分解质因数，设k=p1a1*p2a2...*pmam, 然后计算(s!)=p1b1*p2b2*...*pmbm*...
ans=min(b1/a1,...,bm/am)
#include<iostream>
#include<string>
#include<cassert>
#include<algorithm>
//#include<ctime>
#include<cstring>
#include<cmath>
using namespace std;
//0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
long long powk[63][64]; //2=<k<=62;
int map[128];
int factork[63][63][2];
int prime[18]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};// num is 18
void init()
{
int k,i;
for(k=2;k<=62;k++)
{
powk[k][0]=1;
for(i=1;i<=63;i++)
{
powk[k][i]=powk[k][i-1]*k;
}
}
for(i=0;i<=9;i++)
{
map['0'+i]=i;
}
for(i=0;i<=25;i++)
{
map['A'+i]=10+i;
}
for(i=0;i<=25;i++)
{
map['a'+i]=36+i;
}
for(k=2;k<=62;k++)
{
int tem=k;
int index=1;
for(i=0;i<18;i++)
{
int order=0;
while(tem%prime[i]==0)
{
order++;
tem/=prime[i];
if(tem%prime[i]!=0)
{
factork[k][index][0]=prime[i];
factork[k][index][1]=order;
index++;
}
}
}
factork[k][0][0]=index-1;// the number of k's factorization.
}
}
int main()
{
//time_t _start=clock();
//freopen("input_new","r",stdin);
//freopen("output_new","w",stdout);
init();
char s[100];
int k;
while(scanf("%s %d",s,&k)!=EOF)
{
//printf("%s\n",s);
//cout<<sizeof(s)<<endl;
assert(k<=62&&k>=2);
long long s2dec=0;
for(int i=0;i<strlen(s);i++)
{
s2dec+=map[s[i]]*powk[k][strlen(s)-i-1];
}
assert(log(s2dec*1.0)/log(2.0)<63);
int order[10];
long long num_up=0,num_down=1;
for(int i=1;i<=factork[k][0][0];i++)
{
long long tem=s2dec;
long long ans=0;
while(tem)
{
tem/=factork[k][i][0];
ans+=tem;
}
order[i]=ans;
if(i==1)
{
num_up=ans;
num_down=factork[k][i][1];
}
else if(ans/factork[k][i][1]<num_up/num_down)
{
num_up=ans;
num_down=factork[k][i][1];
}
}
long long output=num_up/num_down;
printf("%lld\n",output);
}
//time_t _end=clock();
//cout<<_end-_start<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}
by quietsmile