Page **1** of **3**

### 10780 - Again Prime? No Time.

Posted: **Tue Nov 23, 2004 12:12 pm**

by **Teapot**

Why WA?

[c]#include <stdio.h>

int getDevidersNumber(int a, int b)

{

int i = 0;

while (0 == (a % b)) {

a = a / b;

i++;

}

return i;

}

int main(void)

{

int i, j, N, m, n, pow;

scanf("%d", &N);

for (i = 1; i <= N; i++) {

scanf("%d %d", &m, &n);

printf("Case %d:\n", i);

if (n == 1) {

printf("0");

} else {

j = m;

pow = 0;

while (j <= n) {

pow += getDevidersNumber(j, m);

j += m;

}

if (pow) {

printf("%d", pow);

} else {

printf("Impossible to divide");

}

}

printf("\n");

}

return 0;

}[/c]

Posted: **Tue Nov 23, 2004 3:23 pm**

by **misof**

If N equals 1, you should output Impossible to divide, as M clearly doesn't divide 1!=1. I'm not going to check the rest of your code (and I doubt that too many people here are willing to do it). The next time please explain the ideas behind your algorithm instead of posting the source.

Posted: **Tue Nov 23, 2004 9:23 pm**

by **Teapot**

Ok. Thanks for your help.

I did not describe idea, because I thought it's pretty simple.

I've used the definition of a factorial.

I check numbers from m to n with step m. And calculate number of dividers equal m (a power of m). Then I add these numbers. Resulting sum is the largest power of m.

It is written in my code:

[c] while (j <= n) {

pow += getDevidersNumber(j, m);

j++;

}[/c]

I have corrected the program according to your tips, but I still receive WA.

Corrected program:

[c]#include <stdio.h>

int getDevidersNumber(int a, int b)

{

int i = 0;

while (0 == (a % b)) {

a = a / b;

i++;

}

return i;

}

int main(void)

{

int i, j, N, m, n, pow;

scanf("%d", &N);

for (i = 1; i <= N; i++) {

scanf("%d", &m);

scanf("%d", &n);

printf("Case %d:\n", i);

j = m;

pow = 0;

while (j <= n) {

pow += getDevidersNumber(j, m);

j += m;

}

if (pow) {

printf("%d", pow);

} else {

printf("Impossible to divide");

}

printf("\n");

}

return 0;

}[/c]

I do not understand what is wrong. Can you give me some test cases?

Posted: **Tue Nov 23, 2004 9:56 pm**

by **Cho**

Teapot wrote:I did not describe idea, because I thought it's pretty simple.

Reading somebody's code is never easy. Please don't post source code only without any idea explained.

I didn't read your code thoroughly, but your idea is wrong.

At least it will fail for the input 10 9. The correct output is 1.

Posted: **Wed Nov 24, 2004 11:48 am**

by **htl**

How about the input/output?

in:

9

3123 2342

234 2343

45 789

111 2222

4999 9999

4999 2

23 6324

454 9022

223 45

out:

Case 1:

6

Case 2:

194

Case 3:

195

Case 4:

61

Case 5:

2

Case 6:

Impossible to divide

Case 7:

285

Case 8:

39

Case 9:

Impossible to divide

Posted: **Wed Nov 24, 2004 12:23 pm**

by **htl**

I got ac....

Posted: **Wed Nov 24, 2004 1:39 pm**

by **Teapot**

Thanks a lot guys! I got AC now.

### 10780 .. Again Prime? No Time.

Posted: **Tue Nov 30, 2004 10:02 pm**

by **muvee**

I'm getting WA .. I've tested the test cases in another thread and they all work. Can you give you your output for these cases and if mine are all correct can you please suggest some other test cases. Thanks.

Input:

Code: Select all

```
7
4500 3
3 4500
4999 9999
2 9999
2 2
5 5
10 10
```

Output:

Code: Select all

```
Case 1:
Impossible to divide
Case 2:
2247
Case 3:
2
Case 4:
9991
Case 5:
1
Case 6:
1
Case 7:
2
```

Posted: **Tue Nov 30, 2004 11:09 pm**

by **muvee**

Here are some further test cases i ran it on.

Input:

50

104 6077

3074 4949

3539 4793

79 6508

3003 5955

2896 8979

2937 3527

629 2235

1017 1573

1844 6419

4911 3829

2041 2358

606 5888

4069 4074

2977 3994

4698 105

2318 8681

1061 7514

1959 4096

733 7567

2947 7851

4684 4680

269 9859

268 1860

2851 9715

547 6972

1730 5320

2906 3082

759 5719

4770 9985

2745 1485

472 5896

358 6460

3315 25

1779 5057

3931 8435

2216 3825

868 4101

3554 3584

4852 3795

259 8733

2745 8034

119 6199

3286 3713

4569 2111

4280 2933

4310 6547

284 1660

599 5714

299 1510

Output:

Case 1:

504

Case 2:

94

Case 3:

1

Case 4:

83

Case 5:

495

Case 6:

49

Case 7:

39

Case 8:

61

Case 9:

13

Case 10:

13

Case 11:

2

Case 12:

15

Case 13:

58

Case 14:

13

Case 15:

17

Case 16:

3

Case 17:

144

Case 18:

7

Case 19:

6

Case 20:

10

Case 21:

18

Case 22:

3

Case 23:

36

Case 24:

27

Case 25:

3

Case 26:

12

Case 27:

30

Case 28:

2

Case 29:

258

Case 30:

191

Case 31:

24

Case 32:

100

Case 33:

36

Case 34:

1

Case 35:

8

Case 36:

2

Case 37:

13

Case 38:

136

Case 39:

2

Case 40:

3

Case 41:

242

Case 42:

133

Case 43:

386

Case 44:

71

Case 45:

1

Case 46:

27

Case 47:

15

Case 48:

23

Case 49:

9

Case 50:

67

Posted: **Wed Dec 01, 2004 9:45 am**

by **Cho**

My AC code gives the same output as yours.

Let's try some boundary cases:

Code: Select all

```
115
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
4995 9995
4995 9996
4995 9997
4995 9998
4995 9999
4996 9995
4996 9996
4996 9997
4996 9998
4996 9999
4997 9995
4997 9996
4997 9997
4997 9998
4997 9999
4998 9995
4998 9996
4998 9997
4998 9998
4998 9999
4999 9995
4999 9996
4999 9997
4999 9998
4999 9999
```

My output:

Code: Select all

```
Case 1:
Impossible to divide
Case 2:
1
Case 3:
1
Case 4:
3
Case 5:
3
Case 6:
4
Case 7:
4
Case 8:
7
Case 9:
7
Case 10:
8
Case 11:
Impossible to divide
Case 12:
Impossible to divide
Case 13:
1
Case 14:
1
Case 15:
1
Case 16:
2
Case 17:
2
Case 18:
2
Case 19:
4
Case 20:
4
Case 21:
Impossible to divide
Case 22:
Impossible to divide
Case 23:
Impossible to divide
Case 24:
1
Case 25:
1
Case 26:
2
Case 27:
2
Case 28:
3
Case 29:
3
Case 30:
4
Case 31:
Impossible to divide
Case 32:
Impossible to divide
Case 33:
Impossible to divide
Case 34:
Impossible to divide
Case 35:
1
Case 36:
1
Case 37:
1
Case 38:
1
Case 39:
1
Case 40:
2
Case 41:
Impossible to divide
Case 42:
Impossible to divide
Case 43:
1
Case 44:
1
Case 45:
1
Case 46:
2
Case 47:
2
Case 48:
2
Case 49:
4
Case 50:
4
Case 51:
Impossible to divide
Case 52:
Impossible to divide
Case 53:
Impossible to divide
Case 54:
Impossible to divide
Case 55:
Impossible to divide
Case 56:
Impossible to divide
Case 57:
1
Case 58:
1
Case 59:
1
Case 60:
1
Case 61:
Impossible to divide
Case 62:
Impossible to divide
Case 63:
Impossible to divide
Case 64:
1
Case 65:
1
Case 66:
1
Case 67:
1
Case 68:
2
Case 69:
2
Case 70:
2
Case 71:
Impossible to divide
Case 72:
Impossible to divide
Case 73:
Impossible to divide
Case 74:
Impossible to divide
Case 75:
Impossible to divide
Case 76:
1
Case 77:
1
Case 78:
1
Case 79:
2
Case 80:
2
Case 81:
Impossible to divide
Case 82:
Impossible to divide
Case 83:
Impossible to divide
Case 84:
Impossible to divide
Case 85:
1
Case 86:
1
Case 87:
1
Case 88:
1
Case 89:
1
Case 90:
2
Case 91:
277
Case 92:
277
Case 93:
277
Case 94:
277
Case 95:
277
Case 96:
8
Case 97:
8
Case 98:
8
Case 99:
8
Case 100:
8
Case 101:
38
Case 102:
38
Case 103:
38
Case 104:
38
Case 105:
38
Case 106:
623
Case 107:
624
Case 108:
624
Case 109:
624
Case 110:
624
Case 111:
1
Case 112:
1
Case 113:
1
Case 114:
2
Case 115:
2
```

Posted: **Wed Dec 01, 2004 11:14 am**

by **muvee**

Thanks Cho! I got AC. I had made a couple of silly mistakes.

My AC has a time for 0.9 seconds.. I was wondering what yours was because I can see some people have done this problem in 0.02 seconds ! If yours is also low, can you please give me some hints on your algorithm?

Thanks.

Posted: **Wed Dec 01, 2004 11:34 am**

by **Cho**

My code takes 0.004s.

I preprocess an array factor[] such that factor* is storing the greatest prime factor of i.*

Then for any m, I find the prime factorization of m. This is easily done in worst case log(m) time by making use of factor[].

For each of m's distinct prime factor p, let a_p = # of factor p in n! / # of factor p in m. # of factor p in n! can be solved by a simple recursive function in log(n) time.

The minimum a_p among all prime factor p of m is the output. And the running time is O(log(m)*log(n))

Posted: **Wed Dec 01, 2004 3:54 pm**

by **muvee**

Thanks Cho.

That is exactly what I did except I did it quite inefficiently!

Thanks again for all your help.

Posted: **Thu Dec 16, 2004 2:53 pm**

by **sumankar**

My algo is as follows:

1. find all primes in [1, 10000]

2. for given (m, n)

a. find prime pk such that m = p1^q1...pk^qk, p1<p2<...<pk

b. find the max power of pk that divides n!

c. find the max power of pk that divides m

3. ans = res of step b / res of step b

Am I wrong?

Suman.

Posted: **Thu Dec 16, 2004 3:22 pm**

by **Eduard**

How have you calculated ??

b. find the max power of pk that divides n!