51nod 1116 K进制下的大数利用同余式的乘法传递性质

发布时间：2020-12-14 03:24:58 所属栏目：大数据来源：网络整理

导读：有一个字符串S，记录了一个大数，但不知这个大数是多少进制的，只知道这个数在K进制下是K - 1的倍数。现在由你来求出这个最小的进制K。例如：给出的数是A1A，有A则最少也是11进制，然后发现A1A在22进制下等于4872,4872 mod 21 = 0，并且22是最小的，因此输

有一个字符串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。

Sample Input

A1A

Sample Output

(z^n)mod m=(z mod m)^n

#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
char s[100005];

int main(){
	//freopen("test.txt","r",stdin);
	int i,j;
	int len;
	int Max;
	int ans;
	int coun=0;
	while(~scanf("%s",s)){
		Max=0;
		len=strlen(s);
		ans=0;
		for(i=0;i<len;i++){
			if(s[i]>='0'&&s[i]<='9')
				s[i]-='0';
			if(s[i]>='A'&&s[i]<='Z')
				s[i]=s[i]-'A'+10;
			if(Max<s[i])
				Max=s[i];
			ans+=s[i];
			//printf("%d ",s[i]);
		}
		//printf("n");
		bool flag=false;
		for(j=Max+1;j<=36;j++){
			if(ans%(j-1)==0){
				flag=true;
				printf("%dn",j);
				break;
			}
		}
		if(!flag)
			printf("No Solutionn");
	}
	return 0;
}

（编辑：李大同）

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

51nod 1116 K进制下的大数 利用同余式的乘法传递性质

51nod 1116 K进制下的大数利用同余式的乘法传递性质