Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2520
Amicable Pairs

Time Limit: 5 Seconds      Memory Limit: 32768 KB

An amicable pair (M, N) consists of two integers M, N for which the sum of proper divisors (the divisors excluding the number itself) of one number equals the other. The smallest amicable pair is (220, 284) which has factorizations 220 = 2*2*5*11 and 284 = 2*2*71, and hence S(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 and S(284) = 1 + 2 + 4 + 71 + 142 = 220. Your job is to find the K-th pair for any given k.

Input
The input consists of several test cases, each occupies a line with a positive integer K.

Output
For each test case, output in a line the K-th amicable pair. The two numbers must be in increasing order.

Sample Input:
1
9
14
20
Sample Output:
220 284
63020 76084
100485 124155 
176272 180848


Author: CHEN, Yue
Source: CYJJ's Funny Contest #2, Relaxing on Math
Submit    Status