首页 > 代码库 > 51nod 1116:K进制下的大数
51nod 1116:K进制下的大数
51nod 1116:K进制下的大数
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1116
题目大意:给定一个大数,该数在$K$进制下是$K-1$的倍数,问最小的$K$($2 \leqslant K \leqslant 36$)是多少,若无解输出No Solution。
二项式定理
这题虽然可以暴力枚举,但还有更优雅的做法。
考虑一个$K$进制的大数$A$可以被表示为$\sum_{x=0}a_xK^x$,
由二项式定理可得$A=\sum_{x=0}a_x(K-1+1)^x=\sum_{x=0}a_x[T(K-1)+1] \equiv \sum_{x=0}a_x(mod K-1)$.
故只需判断各个位上的数字和是否被$K-1$整除即可.
代码如下:
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 string s; 5 int n,w=0; 6 int digit(char c){ 7 if(‘0‘<=c&&c<=‘9‘)return c-‘0‘; 8 return c-‘A‘+10; 9 }10 int main(void){11 cin>>s;12 for(int i=0;i<s.length();++i){13 n+=digit(s[i]);14 w=max(w,digit(s[i]));15 }16 for(int i=w;i<36;++i)if(n%i==0){17 cout<<i+1;18 return 0;19 }20 cout<<"No Solution";21 }
51nod 1116:K进制下的大数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。