10780 - Again Prime? No Time.

Cho · Post by **Cho** » Mon Sep 12, 2005 8:06 am

If you consider the largest prime only, you will fail with N=9, M=48.

georgemouse · Post by **georgemouse** » Mon Sep 12, 2005 3:03 pm

Cho wrote:If you consider the largest prime only, you will fail with N=9, M=48.

My output is 11 ,is it wrong??

9's largest prime factor is 3
48/3=16
16/3=5
5/3=1
16+5+1=22
then 9=3^2
22/2=11

Another way

In 1~48 3's multiples:

3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48
1 1 2 .1 .1 ...2 .1 ...1 .3 ...1 .1 ..2 .1 ..1 .2 .1<-factor 3's amount

1+1+2+1+1+2+1+1+3+1+1+2+1+1+2+1=22
22/2=11

Cho · Post by **Cho** » Mon Sep 12, 2005 4:08 pm

You mis-interpreted the input.
For n=9, m=48, it is asking the largest power k of 48 such that 48^k divides 9!.

georgemouse · Post by **georgemouse** » Tue Sep 13, 2005 3:18 pm

I'm sorry that I mis-interpreted the input.
Thank you!!!

Now I know why I can't accept!!

snar · Post by **snar** » Mon Feb 05, 2007 10:09 pm

Hi all,
Here's my algorithm. Let p be a prime factor of m with power q. Then we can find it's power in (n!). It will be s = n/p + n/p^2 + ...+ n/p^k, where p^k<=n and p^(k+1)>n. The answer will be min{s/q | for each p from m}.

My solution got AC in 0.018 sec. But 0.002 sec is much faster.

dumb dan wrote
Dominik Michniewski wrote:

My algorithm is:

1. generate primes in range [2...5000]
2. for each M,N pair
- factorize M using prime table from step 1
- factorize N! using prime table from step 1
- output (power of max prime in M in N!)/(power of max prime in M) if it's greater than 0 or appropriate message

Is this wrong ?
Only consideringing the max prime factor in M is not enough. Consider cases such as:

Code:
Code: Select all
2 
12 3 
96 96 

It's almost the same as my algorithm, but if it's true, it will be much faster than my solution. So, I'm interested if it's necessary to check all prime factors, or it's enough to do something with the greatest?

Or any other algorithm?

Thanks

snar · Post by **snar** » Mon Feb 05, 2007 10:55 pm

I've made some modifications in finding prime factors and my solution run in 0.004 sec, but what about 0.002 sec?

Thanks

kbr_iut · Post by **kbr_iut** » Sat May 03, 2008 6:15 am

I used this formula
if
i=largest prime factor of m
j =>is such that i^j=m;
then,
nm=n/i;
num+=nm;
while(nm>0){
nm/=i;
num+=nm;
}
num=num/j;
print sum//if sum!=0

my code passes all the dataset of this forum... But I dont know why I am getting WA.pliz anyone help.
here is my code

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#define MAX 5002
bool flag[MAX];

void sieve()
{
   int i,j,k=sqrt(MAX);

   flag[1]=true; 
   for(i=4;i<MAX;i+=2) flag[i]=true; 
   for(i=3;i<=k;i+=2) if(!flag[i]) 
   {
      for(j=i+i;j<MAX;j+=i) flag[j]=true;
   }
}
int main(){
	int i,m,n,num,nm,j,t,T;
	sieve();
	//freopen("10780.txt","r",stdin);
	scanf("%d",&T);
	for(t=0;t<T;t++){
		scanf("%d %d",&m,&n);
		printf("Case %d:\n",t+1);		
		i=2;
		
		while(1){
			if(i>m)break;
			j=0;

			if(!flag[i]&&!(m%i)){
				while(!(m%i)&&m>1){m/=i;j++;}
					
			}
			if(m==1)break;
			i++;
		}
		nm=n/i;
		num=nm;
		while(nm>0){
			nm/=i;
			num+=nm;
		}
		num/=j;


		if(!num)printf("Impossible to divide\n");
		else printf("%d\n",num);
	}
	return 0;
}

Jan · Post by **Jan** » Sat May 03, 2008 2:45 pm

What if the input s like '12 3'?

kbr_iut · Post by **kbr_iut** » Sat May 03, 2008 7:13 pm

i understand. can u tell me is this formula i used wrong? or i misunderstud it...I wrote the formula i used in the previous post.....
i cannt fix it..if u have time pliz help me giving a hints..

Kaidul · Post by **Kaidul** » Sat Dec 29, 2012 8:48 pm

My algorithm is as Follows:

Calculate Factorials upto 5000 by Sieve.
Prime Factorize the given m.
Check the maximum occurrence of each primes of m into n! by a function get_power(int m, int n).
Calculate res = #of total occurrence of a prime in n! / #of total occurrence of a prime in m.
Calculate res for all prime factors in m and res with minimum value is the output.

And My code is http://pastebin.com/mVW1Wzgu

I got WA for a long time and I don't know why.

brianfry713 · Post by **brianfry713** » Sun Dec 30, 2012 9:35 am

input

Code: Select all

AC output:

Code: Select all

Case 1:
1
Case 2:
29
Case 3:
13
Case 4:
40
Case 5:
Impossible to divide
Case 6:
7
Case 7:
9
Case 8:
1
Case 9:
14
Case 10:
Impossible to divide
Case 11:
3
Case 12:
100
Case 13:
80
Case 14:
2
Case 15:
43
Case 16:
85
Case 17:
15
Case 18:
6
Case 19:
6
Case 20:
102
Case 21:
4
Case 22:
34
Case 23:
57
Case 24:
76
Case 25:
21
Case 26:
213
Case 27:
121
Case 28:
35
Case 29:
Impossible to divide
Case 30:
88
Case 31:
710
Case 32:
13
Case 33:
335
Case 34:
Impossible to divide
Case 35:
15
Case 36:
236
Case 37:
28
Case 38:
165
Case 39:
2
Case 40:
Impossible to divide
Case 41:
2
Case 42:
40
Case 43:
24
Case 44:
20
Case 45:
2
Case 46:
4
Case 47:
9
Case 48:
481
Case 49:
58
Case 50:
28
Case 51:
6
Case 52:
54
Case 53:
441
Case 54:
21
Case 55:
23
Case 56:
483
Case 57:
86
Case 58:
21
Case 59:
149
Case 60:
21
Case 61:
184
Case 62:
7
Case 63:
81
Case 64:
11
Case 65:
13
Case 66:
212
Case 67:
50
Case 68:
16
Case 69:
26
Case 70:
Impossible to divide
Case 71:
158
Case 72:
Impossible to divide
Case 73:
35
Case 74:
301
Case 75:
56
Case 76:
2
Case 77:
1
Case 78:
Impossible to divide
Case 79:
155
Case 80:
4
Case 81:
9
Case 82:
296
Case 83:
9
Case 84:
127
Case 85:
1430
Case 86:
26
Case 87:
9
Case 88:
94
Case 89:
27
Case 90:
7
Case 91:
Impossible to divide
Case 92:
635
Case 93:
Impossible to divide
Case 94:
26
Case 95:
1
Case 96:
2
Case 97:
489
Case 98:
3
Case 99:
3
Case 100:
3
Case 101:
13
Case 102:
673
Case 103:
104
Case 104:
1
Case 105:
7
Case 106:
6
Case 107:
27
Case 108:
75
Case 109:
51
Case 110:
Impossible to divide
Case 111:
868
Case 112:
10
Case 113:
391
Case 114:
26
Case 115:
84
Case 116:
44
Case 117:
4
Case 118:
18
Case 119:
13
Case 120:
3
Case 121:
105
Case 122:
1
Case 123:
126
Case 124:
174
Case 125:
1
Case 126:
8
Case 127:
78
Case 128:
4
Case 129:
391
Case 130:
119
Case 131:
17
Case 132:
1
Case 133:
714
Case 134:
30
Case 135:
24
Case 136:
44
Case 137:
67
Case 138:
21
Case 139:
19
Case 140:
58
Case 141:
229
Case 142:
1241
Case 143:
30
Case 144:
248
Case 145:
333
Case 146:
12
Case 147:
97
Case 148:
40
Case 149:
15
Case 150:
59
Case 151:
40
Case 152:
4
Case 153:
20
Case 154:
27
Case 155:
70
Case 156:
101
Case 157:
11
Case 158:
10
Case 159:
19
Case 160:
485
Case 161:
353
Case 162:
291
Case 163:
1807
Case 164:
Impossible to divide
Case 165:
1
Case 166:
89
Case 167:
16
Case 168:
81
Case 169:
Impossible to divide
Case 170:
120
Case 171:
241
Case 172:
487
Case 173:
40
Case 174:
3
Case 175:
133
Case 176:
281
Case 177:
113
Case 178:
Impossible to divide
Case 179:
99
Case 180:
382
Case 181:
11
Case 182:
5
Case 183:
Impossible to divide
Case 184:
10
Case 185:
6
Case 186:
7
Case 187:
74
Case 188:
83
Case 189:
1536
Case 190:
32
Case 191:
282
Case 192:
1
Case 193:
13
Case 194:
17
Case 195:
51
Case 196:
27
Case 197:
154
Case 198:
37
Case 199:
2
Case 200:
10
Case 201:
393
Case 202:
2
Case 203:
1
Case 204:
7
Case 205:
106
Case 206:
7
Case 207:
77
Case 208:
19
Case 209:
16
Case 210:
13
Case 211:
4
Case 212:
1070
Case 213:
7
Case 214:
16
Case 215:
1
Case 216:
30
Case 217:
165
Case 218:
2
Case 219:
62
Case 220:
1
Case 221:
399
Case 222:
69
Case 223:
Impossible to divide
Case 224:
57
Case 225:
114
Case 226:
5
Case 227:
28
Case 228:
204
Case 229:
211
Case 230:
13
Case 231:
8
Case 232:
70
Case 233:
677
Case 234:
1
Case 235:
2
Case 236:
6
Case 237:
3
Case 238:
4
Case 239:
13
Case 240:
9
Case 241:
1
Case 242:
38
Case 243:
581
Case 244:
44
Case 245:
167
Case 246:
620
Case 247:
141
Case 248:
2
Case 249:
1548
Case 250:
Impossible to divide
Case 251:
131
Case 252:
5
Case 253:
1
Case 254:
2
Case 255:
749
Case 256:
821
Case 257:
22
Case 258:
895
Case 259:
54
Case 260:
252
Case 261:
3
Case 262:
Impossible to divide
Case 263:
20
Case 264:
35
Case 265:
59
Case 266:
10
Case 267:
19
Case 268:
84
Case 269:
89
Case 270:
24
Case 271:
200
Case 272:
49
Case 273:
142
Case 274:
428
Case 275:
129
Case 276:
46
Case 277:
99
Case 278:
22
Case 279:
7
Case 280:
121
Case 281:
12
Case 282:
1
Case 283:
23
Case 284:
26
Case 285:
124
Case 286:
713
Case 287:
103
Case 288:
7
Case 289:
36
Case 290:
16
Case 291:
39
Case 292:
68
Case 293:
9
Case 294:
1
Case 295:
114
Case 296:
3
Case 297:
173
Case 298:
433
Case 299:
Impossible to divide
Case 300:
14
Case 301:
109
Case 302:
11
Case 303:
2
Case 304:
87
Case 305:
56
Case 306:
167
Case 307:
130
Case 308:
Impossible to divide
Case 309:
6
Case 310:
6
Case 311:
3
Case 312:
160
Case 313:
11
Case 314:
3
Case 315:
36
Case 316:
78
Case 317:
12
Case 318:
36
Case 319:
169
Case 320:
12
Case 321:
1
Case 322:
14
Case 323:
5
Case 324:
584
Case 325:
32
Case 326:
113
Case 327:
168
Case 328:
9
Case 329:
322
Case 330:
207
Case 331:
309
Case 332:
5
Case 333:
126
Case 334:
68
Case 335:
54
Case 336:
Impossible to divide
Case 337:
107
Case 338:
83
Case 339:
80
Case 340:
54
Case 341:
95
Case 342:
17
Case 343:
48
Case 344:
3
Case 345:
1
Case 346:
1394
Case 347:
3
Case 348:
295
Case 349:
1
Case 350:
32
Case 351:
49
Case 352:
5
Case 353:
26
Case 354:
1
Case 355:
Impossible to divide
Case 356:
3
Case 357:
788
Case 358:
34
Case 359:
163
Case 360:
18
Case 361:
5
Case 362:
525
Case 363:
3
Case 364:
38
Case 365:
369
Case 366:
355
Case 367:
5
Case 368:
460
Case 369:
29
Case 370:
827
Case 371:
107
Case 372:
Impossible to divide
Case 373:
287
Case 374:
18
Case 375:
96
Case 376:
48
Case 377:
125
Case 378:
12
Case 379:
2
Case 380:
Impossible to divide
Case 381:
17
Case 382:
53
Case 383:
23
Case 384:
Impossible to divide
Case 385:
18
Case 386:
29
Case 387:
3
Case 388:
25
Case 389:
129
Case 390:
2
Case 391:
10
Case 392:
8
Case 393:
21
Case 394:
Impossible to divide
Case 395:
92
Case 396:
68
Case 397:
1
Case 398:
81
Case 399:
28
Case 400:
908
Case 401:
39
Case 402:
2
Case 403:
1
Case 404:
25
Case 405:
42
Case 406:
7
Case 407:
22
Case 408:
2
Case 409:
Impossible to divide
Case 410:
230
Case 411:
411
Case 412:
110
Case 413:
6
Case 414:
3
Case 415:
116
Case 416:
329
Case 417:
92
Case 418:
Impossible to divide
Case 419:
338
Case 420:
42
Case 421:
10
Case 422:
167
Case 423:
431
Case 424:
145
Case 425:
575
Case 426:
13
Case 427:
74
Case 428:
39
Case 429:
1
Case 430:
47
Case 431:
30
Case 432:
48
Case 433:
84
Case 434:
Impossible to divide
Case 435:
11
Case 436:
892
Case 437:
58
Case 438:
691
Case 439:
7
Case 440:
33
Case 441:
202
Case 442:
369
Case 443:
12
Case 444:
1
Case 445:
31
Case 446:
78
Case 447:
13
Case 448:
5
Case 449:
40
Case 450:
115
Case 451:
47
Case 452:
62
Case 453:
190
Case 454:
3
Case 455:
7
Case 456:
18
Case 457:
9
Case 458:
87
Case 459:
24
Case 460:
43
Case 461:
Impossible to divide
Case 462:
10
Case 463:
74
Case 464:
666
Case 465:
77
Case 466:
Impossible to divide
Case 467:
12
Case 468:
4
Case 469:
104
Case 470:
3
Case 471:
364
Case 472:
3
Case 473:
123
Case 474:
27
Case 475:
11
Case 476:
1
Case 477:
2
Case 478:
Impossible to divide
Case 479:
13
Case 480:
43
Case 481:
242
Case 482:
164
Case 483:
1
Case 484:
15
Case 485:
476
Case 486:
Impossible to divide
Case 487:
11
Case 488:
1
Case 489:
28
Case 490:
3
Case 491:
193
Case 492:
571
Case 493:
224
Case 494:
90
Case 495:
Impossible to divide
Case 496:
188
Case 497:
27
Case 498:
1
Case 499:
23
Case 500:
18

OJ Board

10780 - Again Prime? No Time.

WA..10780 - Again Prime? No time(passes all dataset of board

Re: 10780 - Again Prime? No time

Re: 10780 -I understand the fault but cannt fix it,,hav u time?

Re: 10780 - Again Prime? No time

Re: 10780 - Again Prime? No time