Product of divisorsProblem code: D1 |
All submissions for this problem are available.
A tutorial for this problem is available here
Being in love with number theory, Johnny decided to take a number theory course. On the first day, he was challenged by his teacher with the following problem: given a number N, compute the product of its positive divisors. Johnny is desperate to impress his new teacher so he asks you for help.
In this problem, the divisors of N do not include the number N itself. For example, if N=12, the divisors of N (excluding N) are 1, 2, 3, 4, and 6. Thus, the product of divisors is 1x2x3x4x6=144. Since the result may be very large, if the result has more than 4 decimal digits, Johnny only needs to compute the last 4 digits of it.
Input
The first line contains t, the number of test cases (about 300,000). Then t test cases follow.
Each test case contains a single integer N (1<=N<=500,000) whose product of divisors needs to be computed.
Output
For each test case, print a single line containing the corresponding result of that test case.
Example
Input 6 3 4 12 25 957 10000 Output 1 2 144 5 7493 0000
| Author: | admin |
| Date Added: | 5-05-2009 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
what should be the answer for 1
obviously, ans for 1 is 1.
I'm not so sure. I'm getting wrong answer although I've checked my program with the output of a brute force program for 1 to 500,000. Perhaps I'm doing something wrong with the formatting but I've checked it many times. I guess there is an issue with outlier cases.
why it is obvious ? the divisors of N do not include the number N itself
then set is empty when what is product of members of set ?
sounds cryptic
@Kundan
I had a similaar issue, its certainly not obvious. But Bharat is right. The answer for 1 is 1.
@Vijay .... I also checked all the answers by brute force and its the same... i took the number of testcases to be 500,000 and then checked for all number till 500000.
I was only doubtful about 1. So is there any way that i can check if i have mistaken in the output format
The time limit of n seconds is for the entire test case right, as in if there are 10 test cases all 10 have to be solved in n seconds?
@divyanshu: The empty product is taken to be 1. Like the empty sum is 0. Like anything to the power 0 is 1. Like 0 times anything is 0.
Last line of output is "0000".why??
Why can't it be "0". Just to check for output format errors :)
sm1 plz temme
because the product is greater than 9999 and its last 4 digits are '0000'.
Time Limit Exceeded.... Wat may b d reasons for this issue ? Can any1 plz tel me ??
In java, outputting 300000 values itself taking time. I did even use BufferedOutputStream....
hey guys I'm new here. I write my code in C. But the program works somewhat differently for different compilers. Its mentioned that here gcc 4.0.0-8 is used. Can anyone tell me how to get it?
In C , outputting 300000 values without any calculation gave me TLE, don't now what to do then
any ideas in c to reduce time
don't use cin\cout
Even I don't understand this . How can one output 300000 values within two seconds ? Is 2 seconds , the time limit for a single test case or for all cases included ? Please clear my doubt Chef .. !!
In Java, While program logic taking 0.8S, outputting the values taking more than 3.2s causing TLE
@Anoop kumar, you are damaging spirit of contest. please do not post code.
@Rahul Gulati
At least 40 people have done it. 2 seconds is time limit for all test cases included I think.
@Ajay
Thanks :) I was thinking of that only ..
hey i've checked my program using the brute force method but still it is saying incorrect answer... i checked for all the cases but all of them are correct.. any suggestions about in which test case the program would've failed.. or is it some formatting error ??
hey guys I'm new here. I write my code in C. But the program works somewhat differently for different compilers. Its mentioned that here gcc 4.0.0-8 is used. Can anyone tell me how to get it?
I checked the solutions many times, still showing wrong answer. What could be the problem.
i have a solution which comes around 1.8 secs .. but strangely the codechef system keeps rejecting it for TLE... Anyone has any ideas on this ???
@Yogesh The server config might not be the same as yours and hence you can assume the server to be slower.
hey guys I see you ppl do it differently
For 957 with factors 3, 11, 29 the product of divisors is 915849
but the answer is given is 7493. Though doable I guess you should be considering both solutions.
OOPssssssss My mistake Sorry guys........ :D
might be some prob with evaluater,
it says time limit exceed, and i checked it I found wrong output was given by the pro, instead of showing correct respose i.e. wrong answer it is displaying time limit exceed , how to become sure weather really time limit exceed or test case failed
wat does runtime error NZEC means?
i have used python 2.6 instead of 2.5 as given in the options for languages here, is that creating a problem?
the code runs well on my system!
whts wrong with the system???
I jst tried to output default answer without calculating anything..
but just to output the answer it is saying time limit exceeded!!!!
plz help me !!
question posted earlier.
^you can check for it in the help section.
i cant find help there.
the code is running properly giving correct output for the given example inputs!!!!
HELP!!!!!!!!!!
are there compilers available for python language or i m wasting my time here!!!!!!
Program is working on my pc but here it is reporting SIGSEGV error, help.
Made necessary changes but still the same.
Some of you guys may feel that the time limit is slightly restrictive, but a well coded solution will be accepted. That is the intent of this problem.
Has the submission been stopped? But I can see some members have submitted some hours back!
Please help me if I am missing something!!!
can i submit the code now.
i just want to check whetreh my code is good.?
Why is the solution submission option removed? We can still see few users uploading their solutions. Please let us know. Your response would be highly appreciated
Very simple