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

大数取模 O(36*n)的方法很容易想 O(n)的就很脑洞了…

S=a[n]*k^n+a[n-1]*k^(n-1)+....+1 a[n]*k^n=a[n]*(k-1+1)^n =a[n]*(1+C(n,1)(k-1)+C(n,2)*(k-1)^2....+C(n,n)*(k-1)^n) 令t[n]=C(n,1)(k-1)+C(n,2)*(k-1)^2....+C(n,n)*(k-1)^n a[n]*k^n=a[n]*(1+t[n])=a[n]+t[n]*a[n] 显然t[n]%(k-1)=0 S=a[n]*t[n]+a[n]+a[n-1]*t[n-1]+a[n-1]+...... 如果a[n]+a[n-1]+a[n-2]+a[n-3]+... %(k-1)=0 S%(k-1)=0 //O(n) #include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<bitset> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 const int N=1e5+5; char s[N]; int main() { //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); scanf("%s",s); int st=0,n=strlen(s); int sum=0; for(int i=0;i<n;++i){ if(isdigit(s[i])) s[i]-='0'; else s[i]+=10-'A'; sum+=s[i]; st=max((int)s[i],st); } for(int i=st;i<36;++i) if(sum%i==0){ cout<<i+1<<endl; return 0; } cout<<"No Solution"<<endl; return 0; } //O(36n) #include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<bitset> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 const int N=1e5+5; char s[N]; int mod(int n,int k){ int ans=0; for(int i=0;i<n;++i){ ans=ans*k+s[i]; ans%=(k-1); } return ans; } int main() { //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); scanf("%s",s); int st=0,n=strlen(s); for(int i=0;i<n;++i){ if(isdigit(s[i])) s[i]-='0'; else s[i]+=10-'A'; st=max((int)s[i],st); } for(int i=st+1;i<37;++i) if(mod(n,i)==0){ cout<<i<<endl; return 0; } cout<<"No Solution"<<endl; return 0; }