进制 base.cpp

【一句话题意】给数p、q、r，已知p、q为十进制数，求最小的b使得在b进制下p*q的值等于r。 令t为t在b进制下的值。p、q、t<=10¹⁸。有1e4个询问。2<=b<=16，保证有解。 【分析】最直观的算法当然是高精度运算，每次从2~16枚举b的值，直接暴力即可。但这样编程复杂度奇高，想我这种既懒，又差错能力低下的人是很不适合的。 再对题面进行分析，因为t小于1e18且保证有解，所以必然有$t=r_{(b)}=p_{(10)}\ast q_{(10)}$。先将r以数组的形式进行保留，再从小到大枚举b，用longlong储存并与p * q进行比较即可。 考场错误：此题没有静态差错，数组大小应根据最小（大）数的来定。因为小于1e18的二进制数最多有60位，所以要开大于60的数组，而不是40。 【code】

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int T,len; long long p,q; char t[60]; long long ans,res; inline int check(){ ans=p*q; for(int k=2;k<=16;k++){ res=0; for(int i=1;i<=len;i++) res=res*k+(t[i]-'0'); if(res==ans) return k; } return 0; } int main(){ // freopen("base.in","r",stdin); // freopen("base.out","w",stdout); cin>>T; while(T--){ memset(t,0,sizeof(t)); scanf("%lld%lld%s",&p,&q,t+1); len=strlen(t+1); printf("%d\n",check()); } return 0; }