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
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
You can now submit your solutions here: http://www.codechef.com/problems/D1/
whenever i download the solutions written by others in C given in the right hand corner it never runs in the turbo c compiler. it always fails to run and shows general protection exception. how this programs are correct when they dont run ( very sorry to doubt the genuis of the coders behind these programs ). please can someone tell me how to make them run.
CodeChef uses the gcc compiler.
Why such large number of test cases and values of numbers are given as MAX limit?
@harshvardhan To make the problem interesting :)
The problem example illustrates the product of divisors of 957 to be 7493. But i am running my code for N=957 and the list of divisors I am getting is 1,3,11, 29, 33, 87, 319 and product of divisors is 876467493.
should the output also contain at maximum, the last 4 digits?
Read the problem statement carefully. You have to print only the last 4 digits of the product.
ok....i got it. the result should be computed to last 4 digits. but suppose if the input data itself contains more than 4 digits, then should computation be performed over the divisors of last four digits of that number or the entire number? like.. if N=34536, then computation should be done on divisors of 34536 or 4536?
For the divisors of the entire number.
What will be the input? will
You have to read the input
what other than dividing by
what other than dividing by zero can cause a divide error?
and what is a NZEC error?
Please read the FAQ
Please read the FAQ
can you pls take a look at
can you pls take a look at solution no. 103733.
i have tried for a long time now but can't find the error.
pls. take a look at it.
waiting for a reply
I don't like to read through
I don't like to read through other people's codes. I've got the "right idea" about this problem but however I try, I can't beat the time limit. Mine takes 5 sec on my computer.
Can someone give me a link to the right algorithm?
It is linked to from the top
It is linked to from the top of the problem statement :P
admins can you manually check
admins can you manually check out the last codes I sent? I'm running the same input that contains all the numbers from 1 to 500000 for both mine and the accepted solutions and i get the same result. (i check it with diff) And i use the same compiler like you guys.
With an input of 500000 it
With an input of 500000 it seems you will work with numDivisors[500000] which is outside the array bounds and can have unexpected results, so that will definitely cause wrong answer. May be other issues, but worth fixing that first.
I fixed that already, doesnt
I fixed that already, doesnt seem to work anyways, but thx for replying.
Solution:131437-When
Please read the FAQ and the
Please read the FAQ and the wiki at www.codechef.com/wiki
@admin I am trying to submit
@admin I am trying to submit my solution in php. Can you please tell me how I can optimize my code. Can I post my code here?
I submitted solutions for some other problems which takes a lot of memory for php in comparison to c. for same algo, I also had the timeout error for the same code of C/C++/Jave (Successfully compiled programs) written by some1 else when I change the syntax to PHP
@Rohit: PHP is slow, and it
@Rohit: PHP is slow, and it seems the online judge doesn't give it any allowance for that as it does for Python and Java. you might want to consider using another scripting language. read the FAQ about posting code; you can post a link to your submission.
@bezgin: here's an idea,
@bezgin: here's an idea, based on my experiences with this problem: if your program is expecting a single Unix-style newline char at the end of each line, that could be the cause of the "Wrong Answer". after fixing that, my program is still too slow, so can't be sure that's the only bug on my end.
finally wrote a little test program to see which testcase files have DOS-style newlines, and put #ifdef ONLINE_JUDGE conditionals to take care of the extra getchar(), so my programs don't have to check at runtime.
@Rohit, my bad, rereading the
@Rohit, my bad, rereading the FAQ says PHP is allowed 3 times the time limit. google 'php profiler' for some suggestions on how to determine the best way to speedup your code.
and what answer do you expect
and what answer do you expect for input of 1
@Shaurya: the judge expects a
@Shaurya: the judge expects a "1" for "1". verified with Neelotpal's program.
@John Comeau thanks a lot....
@Rohit: I haven't had a
@Rohit: I haven't had a successful entry myself yet! And in any case I won't help in that way. I believe in giving guidance where I can, but that doesn't extend to debugging or optimizing other people's programs.
my code is working just fine
my code is working just fine with small numbers.However when they get bigger like 10000, the product of the divisors becomes 10000^(12)/100 which my computer cannot compute. Please consider me as a noob. It's said that computing last 4 digits would be enough,but i can just compute the whole value itself with my code,which goes beyond the limits.
Any suggestions,please...
You cannot (at least, should
You cannot (at least, should not) solve this problem by calculating the exact value of the product of divisors and then printing out the last 4 digits. Google for modular arithmetic.
Then it's gonna be harder for
Then it's gonna be harder for me:) Thank you.
What will be out put for
What will be out put for input 500000 or greater?
@Admin : What will be out put
@Admin : What will be out put for input 500000 or greater?I meant what will be the outcome in case of inpout is maximum limit or more?
The problem statement says
The problem statement says the input won't be larger than 500000.
i dont know ....... my
i dont know ....... my program is giving result of 500000 without consuming a millisecond... and here i am getting TLE.. :(
some check solution of
some check solution of neelotpal dhar ...... lol its damn so BIG.. 387 lines... lmao
it seems as if a simple
it seems as if a simple problem but its really terrrrible!
before attempting the problem i thought it would be easy..hats off to ones who have solved these.........................
anyway giving up tehse challenges would be a great loss.......
mine program too gives result
mine program too gives result ,but TLE makes a lot of trouble.............................can anyone suggest how to reduce time limit?
i am not able to post my
i am not able to post my solution
the submit button doesn't redirect to the proper page
please see
still the submit button is
still the submit button is not steady
it sometimes shows the page and many times doesnt
please correct it quickly
I am getting TLE. Following
I am getting TLE. Following is the code.
long get_me_product(long num)
{
long sprod=1;
long prod=1;
for(long i=2;i*i<=num;i++)
{
if(num%i==0)
{
long j=num/i;
if(i!=j)
prod=((prod%10000)*(i%10000)*(j%10000))%10000;
else
prod=((prod%10000)*(i%10000))%10000;
}
}
return prod;
}
How can I optimize this code to bypass TLE? Any help will be appreciated
r = input() yy = [] for x in
#include #include int