SPOJ.com - Problem INVDIV

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)

Submit solution!

hide comments

< Previous 1 2 Next >

	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 ~210^9, my AC solution is 210^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.

Submit solution!

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