INVDIV - Smallest Inverse Sum of Divisors

no tags 

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

For 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 integer per line.)

Output

For each test case, output the 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
Ishan: 2022-04-10 15:36:41

@Tjandra, Can you please share one of the test cases where my submission 29421107 is giving wrong answer.
Edit:- Nevermind found the bug, it was an overflow issue. Really nice problem. You have to be lot faster than Nlog N . Nlog N comes to be ~2*10^9, my AC solution is 2*10^6

Last edit: 2022-04-25 14:40:32
princemishra: 2020-12-23 10:49:38

can someone tell upto which limit i should find the sum of divisors??

shakil_nstu: 2020-11-02 08:56:52

You need O(NloglogN) to solve this problem.

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
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.


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