K进制下的大数字符串取模

有一个字符串S，记录了一个大数，但不知这个大数是多少进制的，只知道这个数在K进制下是K - 1的倍数。现在由你来求出这个最小的进制K。 例如：给出的数是A1A，有A则最少也是11进制，然后发现A1A在22进制下等于4872,4872 mod 21 = 0，并且22是最小的，因此输出k = 22(大数的表示中A对应10，Z对应35)。

Input 输入大数对应的字符串S。S的长度小于10^5。 Output 输出对应的进制K，如果在2 - 36范围内没有找到对应的解，则输出No Solution。 Sample Input

A1A

Sample Output

22

主要考察字符串取模问题，从最小数字开始枚举。 取模流程我们每次只需要乘以它的进制位数，然后一次累加进行取模就ok了，因为取模运算可以分开计算。

#include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<math.h> #include<deque> #include<set> using namespace std; const int M=10000; int dig[100055]; char cdig[100055]; int main() { scanf("%s",cdig); int flag=0; int maxs=-1; int len=strlen(cdig); for(int i=0;i<len;i++) { if(cdig[i]>='A') { maxs=max(maxs,cdig[i]-'A'+10); } else { maxs=max(cdig[i]-'0',maxs); } } for(int i=maxs+1;i<=36;i++) { int sum=0,cnt; for(int j=0;j<len;j++) { if(cdig[j]>='A') { cnt=cdig[j]-'A'+10; } else { cnt=cdig[j]-'0'; } sum=(sum*i+cnt)%(i-1); } if(sum==0) { cout<<i<<endl; flag=1; break; } } if(!flag) { puts("No Solution"); } }