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

思路:

比如数字为ABCD, 则可以表示为:(A * (K ^ 3) + B * (K ^ 2) + C * K + D) % (K - 1) == 0。 又因为K % (K - 1) == 1; 因此得到(A + B + C + D) % (K - 1) == 0;

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 10;
char input[MAXN];

int main()
{
    cin >> input;
    int len = strlen(input);
    int minK = 2;
    int sum = 0;
    for (int i = 0; i < len; i++)
    {
        if (input[i] <= '9' && input[i] >= '0')
        {
            sum += input[i] - '0';
            if (input[i] - '0' + 1 > minK)
            {
                minK = input[i] - '0' + 1;
            }
        }
        else
        {
            sum += input[i] - 'A' + 10;
            if (input[i] - 'A' + 11 > minK)
            {
                minK = input[i] - 'A' + 11;
            }
        }
    }
    
    bool found = false;
    for (int i = minK; i <= 36; i++)
    {
        if (sum % (i - 1) == 0)
        {
            found = true;
            cout << i << endl;
            break;
        }
    }
    
    if (!found)
    {
        cout << "No Solution" << endl;
    }
    
	return 0;
}
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院