51nod 1116 K进制下的大数 （暴力枚举）
发布时间：2020-12-14 02:12:55 所属栏目：大数据 来源：网络整理
导读：有一个字符串S，记录了一个大数，但不知这个大数是多少进制的，只知道这个数在K进制下是K - 1的倍数。现在由你来求出这个最小的进制K。 例如：给出的数是A1A，有A则最少也是11进制，然后发现A1A在22进制下等于4872,4872 mod 21 = 0，并且22是最小的，因此输
|
有一个字符串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]=' ';
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("%dn",ans);
else printf("No Solutionn");
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |