傳送門
1116 K進制下的大數
基準時間限制：1 秒 空間限制：131072 KB 分值: 20 難度：3級算法題 收藏 關注
有1個字符串S，記錄了1個大數，但不知這個大數是多少進制的，只知道這個數在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
解題思路：
其實我們就是枚舉從出現的最大的數+1開始枚舉，1直到36結束，然后基本操作就是對字符串取模，1個字符串進行取模，我們每次只需要乘以它的進制位數，然后1次累加進行取模就ok了，由于取模運算可以分開計算。（其實這個題我覺得主要是考察字符串取模的問題）
上代碼：
#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下，其實不用特判也能過)
{
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網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
