51Nod 1116 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

 

 

 

 

 

 

 

 

AC代码：

 

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; char ch[100005]; int exchange(char a) { if(a == '0') return 0; else if(a == '1') return 1; else if(a == '2') return 2; else if(a == '3') return 3; else if(a == '4') return 4; else if(a == '5') return 5; else if(a == '6') return 6; else if(a == '7') return 7; else if(a == '8') return 8; else if(a == '9') return 9; else { return (a - 'A' + 10); } } int pow_(int a, int b) { int c = 1; for(int i = 1; i <= b; i++) c *= a; return c; } int main() { while(cin>>ch) { int k, sign = 2; long long number = 0; for(int i = 0; i < strlen(ch); i++) { sign = max(sign, exchange(ch[i])); } if(sign == 0 || sign == 1) cout<<"No Solution"<<endl; int i; for(i = sign + 1; i <= 36; i++) { number = 0; for(int j = 0; j < strlen(ch); j++) { number += exchange(ch[j]); } if(number % (i - 1) == 0) { cout<<i<<endl; break; } } if(i > 36) cout<<"No Solution"<<endl; } return 0; }