10780 - Again Prime? No Time.

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
If you consider the largest prime only, you will fail with N=9, M=48.

georgemouse
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan
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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan
I'm sorry that I mis-interpreted the input.
Thank you!!!
Now I know why I can't accept!!

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia
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
Narek Saribekyan

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia
I've made some modifications in finding prime factors and my solution run in 0.004 sec, but what about 0.002 sec?

Thanks
Narek Saribekyan

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

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

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

``````
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 10780 - Again Prime? No time

What if the input s like '12 3'?
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

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

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..
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Kaidul
New poster
Posts: 2
Joined: Fri Dec 28, 2012 10:20 pm

Re: 10780 - Again Prime? No time

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10780 - Again Prime? No time

input

Code: Select all

``````500
2069 4125
3277 3297
1988 976
428 4292
3273 306
601 4483
3247 1840
4441 4705
458 3262
4090 183
1231 4259
1474 6681
3717 4709
2654 2932
2235 6532
1417 9373
3470 5462
1714 5548
2518 8001
2590 3710
1229 5470
4220 7309
2555 4232
159 4006
4067 1745
2726 9831
4233 9997
3632 8131
2518 1255
4968 1963
450 5698
136 222
136 5384
3121 1682
2335 7343
851 8538
1807 3997
2535 3985
4918 5502
1373 319
1174 1692
1661 6070
1588 9884
4942 7260
2683 5729
4688 1215
4656 923
525 3859
4332 2132
1639 4185
4614 4669
3424 5868
161 9740
142 1515
2519 5495
550 4840
156 1040
785 3307
1769 9013
3893 4831
2961 8527
2653 2755
506 1810
2461 1212
358 2402
3367 7676
4664 2666
3443 5259
1578 6875
4999 2803
3731 6361
3106 1319
515 3617
1856 8458
2416 8478
3370 727
1473 920
4457 1874
2444 7188
529 204
3522 5865
2565 5369
4572 1232
3608 5110
40 5734
2421 7150
3305 6193
1261 9150
538 7408
2306 8679
2981 221
1872 7637
3166 1142
634 8450
4124 1745
2003 5238
2500 7845
1618 2901
4178 7883
3188 2529
762 1719
315 4056
4233 8582
4637 8317
1382 5225
2981 1737
1990 5489
762 9582
4859 5764
4931 407
63 5217
2245 4649
95 7065
1991 4750
2727 8489
1351 8599
4204 4309
3263 4582
311 4166
3295 2440
830 8714
4474 3030
3304 7359
754 4920
4793 7919
2246 9046
1411 6479
3986 8617
572 4718
4307 8666
4009 3767
4871 6059
2352 8588
2330 7091
4191 3160
3151 6064
321 7204
3756 6744
2204 578
2883 3507
168 1380
450 9947
2570 7954
4100 9978
2808 4024
3670 4484
803 7009
3275 5335
1821 9618
1410 2772
4972 4584
2965 2878
1533 1463
4734 7335
584 5164
464 2844
2487 9179
2319 7789
4351 4578
4420 7786
351 4254
1705 8770
240 7242
1985 146
4937 8839
584 6455
2259 4261
3492 7888
2531 1181
1089 2428
1872 2901
1250 7800
1991 7302
2741 8265
583 6943
2262 7888
4977 8852
509 108
2158 8169
532 6885
2071 1291
1301 7276
4282 81
1853 1181
2855 3838
398 1396
2774 5347
3201 8147
160 7690
327 3507
2668 7930
633 357
1294 8942
397 6797
1133 5290
4853 5892
1216 2796
427 2307
2693 7582
1707 5920
4250 6308
3622 4219
1433 1505
3103 753
1210 2152
2824 2597
254 9828
1524 2491
3740 277
1454 9644
3334 8041
756 6436
3535 746
2006 1000
1594 835
4122 6926
1113 8628
3803 9836
2701 4541
1658 1172
726 7986
2502 9628
3929 2633
3763 4065
1824 2089
4541 1373
1903 4924
3243 9439
4557 6362
2513 4960
2859 8335
3390 7939
286 8140
4157 7369
3385 1418
1874 6336
2974 5865
3764 3906
2792 4731
4613 6402
4701 2836
2272 2736
1404 6984
4440 1609
3655 7083
1377 9929
2115 6550
3001 6932
14 9307
3313 2243
1474 8721
4782 4093
4274 3702
3676 1858
220 7502
1053 9873
3211 540
324 7174
735 670
570 4567
4652 3584
1993 102
2305 9640
454 8153
296 2177
1765 3656
3544 8602
3108 3068
4575 5407
2214 1024
4884 7216
749 5271
1496 2299
2584 7724
413 7533
4797 1885
2414 7028
1315 5904
1630 1254
2343 8584
1615 232
2347 3916
2872 8282
2987 2680
1848 1257
3360 4292
325 1260
1096 1060
2043 8344
3736 7824
639 2792
1651 8703
2487 7853
2789 5288
3948 5302
4971 5503
651 5226
484 8682
4538 157
3295 9650
882 1329
1714 9938
2062 2687
2134 8506
678 6334
2862 8716
282 6055
1877 344
3636 700
1531 9650
3602 6539
2115 7419
2061 2663
4429 348
597 7291
816 1274
647 7952
4005 3280
2480 5108
2077 862
2362 2133
1094 7940
2908 3962
204 9382
1711 1943
2343 7954
2046 5074
773 7297
3509 9068
4608 1870
3750 4956
590 341
2120 6582
948 5439
2585 2534
3343 2593
4047 7572
781 5883
1616 8162
4601 5789
3502 9853
461 8221
4508 1073
3717 194
4943 7557
720 5590
2311 7423
39 3557
2991 1230
2169 7827
1661 7506
941 4724
3749 4397
2677 3068
2539 830
3098 5944
1728 4740
1124 9682
3956 6890
1253 3279
982 2793
385 5269
3802 7532
4773 1667
4900 4445
2576 7861
4041 2668
3094 7385
4023 4440
1584 8292
1880 4939
4766 1297
1458 3454
3031 8052
1480 3508
1074 8644
1350 1014
1941 8117
3603 3184
1061 879
741 336
137 7336
3827 2092
4458 261
4190 7630
3383 5865
3622 5544
1468 9331
470 6001
3270 225
3846 6902
3412 6998
815 3468
1238 207
4154 6122
565 7749
3209 3231
3052 8915
1038 4877
448 5464
221 638
838 1013
3908 1485
4842 6864
4089 1974
794 2961
3013 2953
3387 3006
4507 223
2002 2771
2793 7424
2655 6488
4501 3954
1997 7144
1643 6083
1519 9897
3996 3337
4391 917
1890 2047
2831 6314
4113 4866
4840 3355
2550 6919
3330 5273
3696 5773
1182 2565
1691 6609
1580 3122
4943 8882
1961 2515
211 6459
2938 5437
2627 5912
3529 2622
4777 3314
88 8945
352 598
4125 8303
796 1538
283 9417
1026 3649
450 2965
1563 6343
1983 1167
3393 886
705 3660
3324 3757
4076 5664
2848 3629
3339 6036
3439 8612
1072 4197
896 1342
1907 7465
4939 3377
4984 1609
1528 1839
4545 8877
870 715
3043 7704
2239 1037
3316 8798
3939 7564
2673 6666
1854 7989
3494 1699
2771 2116
3273 4685
1403 6336
3964 3831
459 5843
2557 7701
4740 9638
4040 2739
4596 4554
4801 7521
3694 4106
4951 1143
4148 834
1533 3170
12 490
41 6629
3985 1366
2723 6030
152 8595
3866 1485
1671 6304
2063 3848
3685 1894
2861 9368
3552 6971
2618 9169
3906 6753
406 2549
1067 56
3971 6839
4526 2043
4157 5768
4344 4264
3437 9328``````
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``````
Check input and AC output for thousands of problems on uDebug!