Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
第一届北京大学游戏对抗邀请赛将与 ACM-ICPC 北京赛区同时举行,丰厚奖金等你来拿!
Base equality
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 838Accepted: 525


Numerous are the moments I as a programmer have been frustrated by the tedious conversions between decimal numbers and hexadecimal ones. Why have we chosen 10 as a base in our everyday numerical presentations, when 16 seems so practically appealing? Obviously because everyone is not the computer geek I am. Maybe some day the world will fully realise the benefits of the hexadecimal system. In the meantime I have to learn to master the base conversions since most of the time numbers do not resemble one another in different bases.

Sometimes peculiar relationships emerge among the different base representations of numbers though. For instance, I noticed just the other day that 104010 * 4 = 104016, i.e. (1*103+0*102+4*101+0*100)*4=(1*163+0*162+4*161+0*160). It made me wonder how often this is the case, that is, the digits of a number in one base, are exactly the same as the digits of a multiple of the number in another base. Formally, let B1 < B2 be positive integers, and a0,a1,…,ak be integers in [0…B1-1]. For which ai’s is there a positive integer c such that


On the first line of input is a positive integer n telling the number of test cases that follow. Each test case is on a line of its own and consists of two integer bases B1, B2, 9 <= B1 < B2 <= 100, and two integer range elements, r1, and r2, 0 < r1 < r2 <= 10000. Notice that all numbers in the input are given in the base 10.


For each test case, there should be one row containing the largest integer i, fulfilling r1 < i < r2, for which there is a positive integer c such that the digits of i in the base B1, are exactly the same as the digits of i*c in the base B2. If no such integer i exists, output the text ‘Non-existent.’.

Sample Input

10 16 1 2000
10 16 1 4999
10 14 10 9999
11 14 10 9999

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator