51Nod 1116 K进制下的大数 数学推导

1116 K进制下的大数

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 20 分
6.  
7. 3级题

有一个字符串S，记录了一个大数，但不知这个大数是多少进制的，只知道这个数在K进制下是K - 1的倍数。现在由你来求出这个最小的进制K。

例如：给出的数是A1A，有A则最少也是11进制，然后发现A1A在22进制下等于4872,4872 mod 21 = 0，并且22是最小的，因此输出k = 22(大数的表示中A对应10，Z对应35)。

 收起

输入

输入大数对应的字符串S。S的长度小于10^5。

输出

输出对应的进制K，如果在2 - 36范围内没有找到对应的解，则输出No Solution。

输入样例

A1A

输出样例

22

分析：

因为题意说：S%（p-1）==0，所以要求各位置上的和为0就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MOD 1000000007
#define N 500005
string s;
int char_int(char ch)
{if(ch<='Z'&&ch>='A'){return ch-'A'+10;}return ch-'0';
}
int main()
{cin>>s;int max_b=0;int sum=0;for(int i=0;i<s.size();i++){sum+=char_int(s[i]);max_b=max(max_b,char_int(s[i]));}for(int i=max_b+1;i<=36;i++){if(sum%(i-1)==0){printf("%d\n",i);return 0;}}printf("No Solution\n");return 0;
}