注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

利用余数的性质求解  

2009-03-26 16:02:09|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

An Easy Problem!

Acceteped : 47   Submit : 246
Time Limit : 1000 MS   Memory Limit : 65536 KB
 

Description

Have you heard the fact "The base of every normal number system is 10" ? Of course, I am not talking about number systems like Stern Brockot Number System. This problem has nothing to do with this fact but may have some similarity.

You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1). You will have to print the smallest possible value for N. The range for N is 2 <= N <= 62 and the digit symbols for 62 based number is (0..9 and A..Z and a..z). Similarly, the digit symbols for 61 based number system is (0..9 and A..Z and a..y) and so on.
 

Input

Each line in the input will contain an integer (as defined in mathematics) number of any integer base (2..62). You will have to determine what is the smallest possible base of that number for the given conditions. No invalid number will be given as input. The largest size of the input file will be 32KB.
 

Output

If number with such condition is not possible output the line "such number is impossible!" For each line of input there will be only a single line of output. The output will always be in decimal number system
 

Sample Input

3
5
A
 

Sample Output

4
6
11
 

Source

uva 10093

 

题目大意:给定一个N进制的数R,且保证R能够被N-1整除,求出N的最小的可能值。

主要思想:假设给定的数为(an,...,a1,a0)。那么题目就是求能使(an*N^n+...+a1*N^1+a0*N^0)%(N-1)==0成立的最小的N为多少。如果将等式左边的值求出来,再和N-1进行运算,时间复杂度很大。在这里我们可以做一些化简。由(a*a)%c==((a%c)*(a%c))%c,以及(a+b)%c==(a%c+b%c)%c结合N%(N-1)==1可得:(an*N^n)%(N-1)==an,那么上面的等式就可以化简为(an+...+a1+a0)%(N-1)==0,现在就只要求线性的和了。

代码如下:

#include<iostream>
#define MAX 1000000
using namespace std;
int xhgToInt(char ch);
char digit[MAX];
int main(){
    int i,j;
    int r;
    char maxDigit;    //用来记录digit中最大的数
    while(cin>>digit){
        maxDigit=0;
        r=0;
        for(j=0;digit[j];j++){     //一边找出maxDigit,一边求和
            r+=xhgToInt(digit[j]);
            if(maxDigit<digit[j])maxDigit=digit[j];
        }
        for(i=xhgToInt(maxDigit)+1;i<=62;i++){   //N进制的数每一位的数值都必须比N大
            if(r%(i-1)==0)break;                           //所以从maxDigit+1进制开始判断
        }
        if(i<=62)cout<<i<<endl;
        else cout<<"such number is impossible!"<<endl;
    }
    return 0;
}
int xhgToInt(char ch){
    if(ch>='0'&&ch<='9')return (ch-48);
    if(ch>='A'&&ch<='Z')return (ch-55);
    if(ch>='a'&&ch<='z')return (ch-61);
}

后记:数学果然很强大!!

  评论这张
 
阅读(367)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017