51NOD 1116 K进制下的大数(字符串取模 + 枚举)

传送门
1116 K进制下的大数
基准时刻限定：1 秒 空间限定：131072 KB 分值: 20 难度：3级算法题 保藏 存眷
有一个字符串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

解题思绪：
着实我们就是列举从呈现的最大的数+1开始列举，一向到36竣事，然后根基操纵就是对字符串取模，一个字符串举办取模，我们每次只必要乘以它的进制位数，然后一次累加举办取模就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)///(在这里特判一下，着实不消特判也能过)
        {
            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;
}

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!