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。      

Input示例

A1A      

Output示例

22      

   暴力枚舉O(36*n)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+100;
char str[maxn];
int a[maxn];
int main()
{
	int n,i,j,ans,t,tt,ttt,mod;
	scanf("%s",str);
	n=strlen(str);
	ans=2;
	j=0;
	for(i=n-1;i>=0;i--) {
		if(str[i]>='0'&&str[i]<='9') {
			a[j]=str[i]-'0';
			ans=max(ans,a[j]+1);
		}
		else {
			a[j]=str[i]-'A'+10;
			ans=max(ans,a[j]+1);
		}
		j++;
	}
	a[j]='\0';
	for(;ans<37;ans++) {
		t=0;
		tt=1;
		mod=ans-1;
		for(i=0;i<n;i++) {
			t=(t+a[i]*tt%mod)%mod;
			tt=tt*ans%mod;
		}
		if(t==0) break;
	}
	if(ans<37) printf("%d\n",ans);
	else printf("No Solution\n");
	return 0;
}