## 11182 - Zeroes III

**Moderator:** Board moderators

### 11182 - Zeroes III

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

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

Suhendry Effendy

O(n) is waaay too slow.

Try also the case:

Yes, but since we are only interested in the factors of F2(n)F2(n) = 1^S(n) . 2^S(n-1) . 3^S(n-2) . ...... . n^S(1)

*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

At last, I got accepted using O(log n . log b). Thank you for your hint

input:
output:
Edit: (add more random testcases). I don't think there's any tricky case in this problem..

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
```

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
```

Last edited by suhendry on Mon Mar 26, 2007 7:50 am, edited 1 time in total.

Suhendry Effendy

Hi,

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

Thanks,

Jos

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

Thanks,

Jos

Jose Santos

http://ctp.di.fct.unl.pt/~jcas

http://ctp.di.fct.unl.pt/~jcas

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

Thanks a lot!! I got in 0.346 sec.

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

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

Jose Santos

http://ctp.di.fct.unl.pt/~jcas

http://ctp.di.fct.unl.pt/~jcas

try this cases also

Code: Select all

```
999999 2
1000000 997
999999 991
0 0
```

166661938317090928

166919023725621

167930784422985

Hope it helps.

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.

Thanks,

Code: Select all

```
//Removed
```

Last edited by erdos on Mon Apr 09, 2007 1:51 pm, edited 1 time in total.

Jose Santos

http://ctp.di.fct.unl.pt/~jcas

http://ctp.di.fct.unl.pt/~jcas

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];
}
```

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,

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,

Jose Santos

http://ctp.di.fct.unl.pt/~jcas

http://ctp.di.fct.unl.pt/~jcas