INVDIV - Smallest Inverse Sum of Divisors

no tags 

First, we define σ(i) = Sum of all positive divisors of i.

example: all positive divisors of 60 = {1,2,3,4,5,6,10,12,15,20,30,60}

so σ(60)=1+2+3+4+5+6+10+12+15+20+30+60=168

Now for the task: given an integer n find smallest integer i such that σ(i)=n.

Input

The first line is an integer T(1 ≤ T ≤ 100,000), denoting the number of test cases. Then, T test cases follow.

For each test case, there is an integer n(1 ≤ n ≤ 100,000,000) written in one line. (one ineger per line)

Output

For each test case, output Smallest Inverse Sum of Divisors of n. if n doesn't have inverse, output -1.

Example

Input:
5
1
16
40
60
168
Output:
1
-1
27
24
60

 

Time Limit ≈ 2.5*(My Program Top Speed)

 

See also: Another problem added by Tjandra Satria Gunawan


hide comments
Scape: 2015-07-25 20:09:22

Nice problem, a naive algorithm (or optimized naive algorithm) will simply not pass. You need something faster than N * log N.

[Lakshman]: 2015-07-25 11:12:08

@Tjandra Satria Gunawan Can you please check my last submission, I have checked several inputs but don't understand for what kind of input I am getting WA.

EDIT1:: Never-mind got AC. there was some overflow issue.

Last edit: 2015-07-26 15:03:08
[Lakshman]: 2014-01-11 19:58:26

Last edit: 2015-07-25 11:10:32
abdou_93: 2013-11-19 14:31:01

@Tjandra..can you tell me if my alg is efficient or not .. id(10504008)..thanks alot :D

Sandeep Pathry: 2013-07-14 13:16:59

@tjandra.. Plz see my code... It takes 11.11s on spoj cube... Chcked it on INVPHI...
Can u give some hint to optimisation...

Snehasish Roy ;): 2012-12-29 10:50:38

@Tjandra: Kindly see submission id: 8370397 and suggest whether my method of filling divsum[] is inefficient or is there another problem with my code !!

Kindly suggest !
<b><u>Ans</b></u>: yes, your method is inefficient... Remember, think about repeated calculation, your code is 2x slower than normal...

RE- Thank you Tjandra for the hint. I tried 2 different methods but still getting TLE :(
Kindly see submission id : 8388879 and suggest whether I am doing repeated calculation here or not?
<b><u>Ans2</b></u>: Ok, I think your code still 2x slower than normal, last hint: try to delete/not to use divsum[] array... My code use invdivsum[] only and consumes 417MB of memory..

RE- Ok... I will try to implement it !!

Last edit: 2013-01-01 19:48:44
Ashish Lavania: 2012-12-21 16:44:03

Same problem as INVPHI.
@Tjandra, Can you please see the codes of any one of them and tell me where the problem lies
<b><u>Ans:</b></u> Wow, in all 100.000 test cases only 25 test cases your program giving wrong answer... Here is one of them:
<u>input:</u> 1555200
<u>your output:</u> 414120
<u>correct ans:</u> 400680
Ashish : Thank you very much! AC:-))

Last edit: 2012-12-21 18:53:17
(Tjandra Satria Gunawan)(曾毅昆): 2012-10-22 07:48:30

AC % Ratio = 7,14%, definitely this is hard problem, but I agree with you too Damian Straszak if you already know the method this is easier than before because limit of seaching is lower.

Damian Straszak: 2012-10-01 18:34:31

I think this one is easier ;) But maybe my methods are so primitive you didn't expect it ;D

Last edit: 2012-10-01 18:35:37
(Tjandra Satria Gunawan)(曾毅昆): 2012-09-29 10:24:21

I bet this problem is harder than before ;-)


Added by:Tjandra Satria Gunawan
Date:2012-09-29
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem