Page 1 of 3

### 10780 - Again Prime? No Time.

Posted: Tue Nov 23, 2004 12:12 pm
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
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
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
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.

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

Posted: Wed Nov 24, 2004 11:48 am

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
I got ac....

Posted: Wed Nov 24, 2004 1:39 pm
Thanks a lot guys! I got AC now.

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

Posted: Tue Nov 30, 2004 10:02 pm
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
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
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
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
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
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
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
How have you calculated ??
b. find the max power of pk that divides n!