Is there any 'advance' number theory involved in this problem?
O(n) is not fast enough. I've tested the judge with O(n) dummy code (input and loop), and it run for 5s . My best algorithm was O(nlog b) using prime factorization, which is obviously give me TLE.
I use this formula:
F2(n) = 1^S(n) . 2^S(n-1) . 3^S(n-2) . ...... . n^S(1)
where S(n) is accumulated sum from 1 to n -> n * (n+1) / 2
Yes, but since we are only interested in the factors of F2(n) related to input b, many of the terms aren't necessary. Think about it. We got accepted during contest, and NO hard number theory is required.
Try also the case:
1000000 2
7th Contest of Newbies Date: December 31st, 2011 (Saturday) Time: 12:00 - 16:00 (UTC) URL: http://uva.onlinejudge.org
by calculating the sums on paper you can find a formula to compute the number of occurences of a given prime in F2(n). But for each prime p you have to sum these occurences for p, p^2, p^3, ...
(Just as you do to determine the number of occurences of a prime p in n!)
These are less then log(n) steps required (stop at p^x>n). As b has less than log(b) distinct prime factors, you are done.
by calculating the sums on paper you can find a formula to compute the number of occurences of a given prime in F2(n). But for each prime p you have to sum these occurences for p, p^2, p^3, ...
(Just as you do to determine the number of occurences of a prime p in n!)
These are less then log(n) steps required (stop at p^x>n). As b has less than log(b) distinct prime factors, you are done.
It is quite weird...
I spent a while thinking on this problem to get to the right formula. My program gives the same output for the extended input provided a few posts below. Even so I get WA.
Probably, for some extreme inputs, in some intermediate calculation the int64 limit is exceeded and that causes an error?
Thanks for the input but my program also gives the same output. So I still have no clue what may be wrong as I've tried many different inputs and the output is correct. I'm posting my source code below if someone is kind enough to spend sometime trying to figure out what might be the problem.
Thank you so much. I've submitted and got accepted.
When I looked at your correction it was immediately obvious. It was a typo, but what's more amazing is that even with that typo the program was giving correct results for any test case posted here!
If it were giving some wrong results it would have been much easier to spot it.
Hello, can anybody please look at my code what exactly goes wrong? All the provided input gave me right output but got WA 3 times. Couldn't find what caused this. Please help me out.