Page 1 of 1

11182 - Zeroes III

Posted: Tue Feb 27, 2007 6:06 am
by suhendry
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 :o . 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

Posted: Tue Feb 27, 2007 8:03 am
by Observer
O(n) is waaay too slow.
F2(n) = 1^S(n) . 2^S(n-1) . 3^S(n-2) . ...... . n^S(1)
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

Posted: Tue Feb 27, 2007 12:44 pm
by deepesh
Can you give the answer for :
1000000 2

Also can you give a few more test cases. I am getting a wrong answer.


[Edit] -> I have got accepted on this problem

Posted: Thu Mar 01, 2007 6:16 am
by suhendry
At last, I got accepted using O(log n . log b). Thank you for your hint :)

input:

Code: Select all

8191 8192
1000000 2
1000000 2310
1000000 6720
1 2
2 864
5 10
10 10000
48 219
100 5
2133 504
2610 30
3248 219
4511 888
8950 66
42610 3000
84511 7323
63702 864
63702 1431
244080 67
955467 6
958356 496
958356 3502
984673 9973
999999 9999
1000000 10
1000000 10000
0 0
output:

Code: Select all

7032662488
166662438307705929
16665402729127869
27776193671899116
0
0
1
5
0
36924
266003535
734253290
75718500
415423766
11886657412
1073649906316
39445538957
7177687067852
826272808535
36682693786847
72686052960360603
4889164417770575
1437645574232012
15713577274647
1666006641512399
41664788608656248
10416197152164062
Edit: (add more random testcases). I don't think there's any tricky case in this problem..

Posted: Thu Mar 22, 2007 3:55 am
by erdos
Hi,

My program outputs the same results but judge returns WA. Could you please provide some additional sample input and output?

Thanks,

Jos

Posted: Mon Apr 02, 2007 9:35 am
by hank
Hello ,
Could you give me some hint about how to reduce the complexity from O(nlogb) to O(lognlogb) ?

since we are only interested in the factors of F2(n) related to input b
What does it mean?
Could you please give me some hints?

Thx in advance! :D

Posted: Mon Apr 02, 2007 9:55 am
by Erik
Hello,

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.

Cu, Erik :)

Posted: Thu Apr 05, 2007 4:10 am
by hank
Erik wrote:Hello,

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.

Cu, Erik :)
Hi , Erik
Thanks a lot!! I got in 0.346 sec.
:P

Posted: Sat Apr 07, 2007 4:46 pm
by erdos
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?

Could you please provide border cases like that?

Thanks,

Jose Carlos

Posted: Sun Apr 08, 2007 4:59 am
by mmonish
I think there's no such tricky cases. I use unsigned long long and get accepted.

try this cases also

Code: Select all

999999 2
1000000 997
999999 991
0 0
Output
166661938317090928
166919023725621
167930784422985

Hope it helps.

Posted: Mon Apr 09, 2007 12:44 am
by erdos
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.

Code: Select all

//Removed
Thanks,

Posted: Mon Apr 09, 2007 9:46 am
by mmonish
I change this portion of u'r code and get AC.

Code: Select all

if(countFactors[i]/bases[i]<min) 
{ 
     min=countFactors[i]/powers[i]; 
}

after change

if(countFactors[i]/powers[i]<min) 
{ 
     min=countFactors[i]/powers[i]; 
}

remove u'r code after AC.

Posted: Mon Apr 09, 2007 1:58 pm
by erdos
Hi,

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.

Thank you again,