51NOD1116 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 这道题有O(n)的做法。 首先呢,kmod(k-1)=1,那么k的幂次方mod(k-1)也为1. 假设s是可以被k-1整除的， 那么S可以看成(a[0]*k+a[1]*k^1+a[2]*k^2+a[3]*k^3...+a[n-1]*k*(n-1)) 为啥这样弄呢，例如(a[i]*k^i)mod(k-1)可以化成a[i]mod(k-1)*k^imod(k-1)=a[i]mod(k-1) 那么可以简化成s=a[0]+a[1]+a[2]+....a[n-1].. 然后从小到大求符合s%(k-1)符合条件的k即可。 #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cctype> #include<cmath> #include<ctime> #include<string> #include<stack> #include<deque> #include<queue> #include<list> #include<set> #include<map> #include<cstdio> #include<limits.h> #define MOD 1000000007 #define fir first #define sec second #define fin freopen("/home/ostreambaba/文档/input.txt", "r", stdin) #define fout freopen("/home/ostreambaba/文档/output.txt", "w", stdout) #define mes(x, m) memset(x, m, sizeof(x)) #define Pii pair<int, int> #define Pll pair<ll, ll> #define INF 1e9+7 #define inf 0x3f3f3f3f #define Pi 4.0*atan(1.0) #define lowbit(x) (x&(-x)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define max(a,b) a>b?a:b typedef long long ll; typedef unsigned long long ull; const double eps = 1e-9; const int maxn = 100000+5; using namespace std; inline int read(){ int x(0),f(1); char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } int main(){ string str; cin>>str; int sum=0; int st=0; int r; for(int i=0;i<str.size();++i){ if(isdigit(str[i])){ r=str[i]-'0'; sum+=r; }else{ r=str[i]-'A'+10; sum+=r; } st=max(st,r); } // cout<<sum<<endl; bool flag=false; for(int i=st;i<=36;++i){ if(sum%i==0){ printf("%d\n",i+1); flag=true; break; } } if(!flag){ puts("No Solution"); } return 0; }