题目大意:从0-9,还有A-Z,a-z,总共62个字母,分别代表62个数字。给出一个数字s(s由给出的62个字母组成),让你求一个最小的进制n,使得n-1能整除s。
输入:给定的数字s
输出:最小的进制n
解题思路:
推导(转载自http://xingfinal.blog.163.com/blog/static/9792456820092310154626/
设输入的是abcd,假设其解是n进制,则有
(a*n*n*n + b*n*n + c*n + d)%(n-1)=0
则有:( (a*n*n*n)%(n-1)+
(b*n*n)%(n-1)+
(c*n)%(n-1)+
d )%(n-1)=0

则有:( (a* (n%(n-1)) *(n%(n-1)) *(n%(n-1)))+
(b* (n%(n-1)) *(n%(n-1)))+
(c* (n%(n-1) +
d ) %(n-1)=0

则有: (a*1*1*1+b*1*1+c*1+d)%(n-1)=0
则有:(a+b+c+d)%(n-1)=0

所以,经过转换,变为求输入数的各数位的和能%(n-1)等于0;

核心代码:

len=strlen(str);
		for(i=len-1;i>=0;i--)
        {
            sum+=rec[str[i]];
			if(maxn<rec[str[i]])
				maxn=rec[str[i]];
        }
        for(i=maxn+1;i<=62;i++)
        {   
            if(sum%(i-1)==0)
            {
                res=i;
                break;
            }
        }

发表评论

电子邮件地址不会被公开。

Post Navigation