Memoirs of Fili and Kili
All submissions for this problem are available.
The journey was a long and arduous one. And most of them started getting bored, sitting on their horses all day with nothing to do. Some of them (read Fili and Kili) were even beginning to be vocal about it. To shut them up, Gandalf decided to give them a puzzle to keep them occupied. Fili and Kili were really good with numbers (so they said), so Gandalf decided to make the problem a little more difficult for them.
Gandalf has an even number of gold coins in his pocket – ‘p’ pairs to be precise and he would provide some clues to Fili and Kili so that they can come up the right answer as to what the value of ‘p’ is.
If there is another number ‘x’ which is divisible by both ‘a’ and ‘b’ such that the product ‘ab’ is equal to ‘x’ itself and aᵠ(b)≡ 1 (mod b) where ᵠ(b) gives the number of positive integers (<=b) that are relatively prime to ‘b’. ‘p’ is equal to the sum of integers present in all such unique pairs. Find ‘p’.
By unique pairs we mean that (a,b) and (b,a) are same so must be considered only once for computation of p.
For a number x let’s say that (a,b,c,d) are it’s factors and (a,b) and (c,d) satisfy the above condition then you have to output a+b+c+d
The first line of the input contains an integer t denoting the number of testcases.
Each testcase contains a single line containing the value of integer x.
For each testcase output a single line containing the value of p.
Input: 3 41 18467 6334 Output: 42 18840 9504
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.