傳送門
1116 K進(jìn)制下的大數(shù)
基準(zhǔn)時間限制：1 秒 空間限制：131072 KB 分值: 20 難度：3級算法題 收藏 關(guān)注
有1個字符串S，記錄了1個大數(shù)，但不知這個大數(shù)是多少進(jìn)制的，只知道這個數(shù)在K進(jìn)制下是K - 1的倍數(shù)。現(xiàn)在由你來求出這個最小的進(jìn)制K。
例如：給出的數(shù)是A1A，有A則最少也是11進(jìn)制，然后發(fā)現(xiàn)A1A在22進(jìn)制下等于4872,4872 mod 21 = 0，并且22是最小的，因此輸出k = 22(大數(shù)的表示中A對應(yīng)10，Z對應(yīng)35)。
Input
輸入大數(shù)對應(yīng)的字符串S。S的長度小于10^5。
Output
輸出對應(yīng)的進(jìn)制K，如果在2 - 36范圍內(nèi)沒有找到對應(yīng)的解，則輸出No Solution。
Input示例
A1A
Output示例
22
解題思路：
其實(shí)我們就是枚舉從出現(xiàn)的最大的數(shù)+1開始枚舉，1直到36結(jié)束，然后基本操作就是對字符串取模，1個字符串進(jìn)行取模，我們每次只需要乘以它的進(jìn)制位數(shù)，然后1次累加進(jìn)行取模就ok了，由于取模運(yùn)算可以分開計(jì)算。（其實(shí)這個題我覺得主要是考察字符串取模的問題）
上代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAXN = 1e5+5;
char s[MAXN];
int main()
{
while(cin>>s)
{
int len = strlen(s), Max = -1;
for(int i=0; i<len; i++)
{
if(s[i]>='A' && s[i]<='Z')
Max = max(Max,(s[i]-'A'+10));
else
{
Max = max(Max,(s[i]-'0'));
}
}
///cout<<Max<<endl;
if(Max == 0)///(在這里特判1下，其實(shí)不用特判也能過)
{
puts("No Solution");
continue;
}
for(int i=Max+1; i<=36; i++)
{
int sum = 0;
for(int j=0; j<len; j++)
{
if(s[j]>='A' && s[j]<='Z')
{
sum = sum*i+(s[j]-'A'+10);
sum %= (i-1);
}
else
{
sum = sum*i+(s[j]-'0');
sum %= (i-1);
}
}
if(sum == 0)
{
cout<<i<<endl;
goto endW;
}
}
puts("No Solution");
endW:;
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
