11182 - Zeroes III

[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 . 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

[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

[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

[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..

[erdos]

Hi,

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

Thanks,

Jos

[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!

[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

[hank]

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.

[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

[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.

[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,

[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.

[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,

[Solitude]

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.

Code: Select all

Removed after AC