10692 - Huge Mods

[helmet]

It seems only 1 AC out of 13 submissions.Am I missing something here?

Can the person who got AC tell if there is some tricks in the input?Maybe some sample I/o?
Are any people who got it during the contest getting WA?

[howardcheng]

I have no idea. I thought I knew how to do it, and I am not sure if my algorithm is wrong or if I have some silly bugs. I knew about special cases and thought I handled them:

- M = 2
- gcd(base, M) > 1

What am I missing?

[rotoZOOM]

I've got AC during contest in first attempt.
There are no special tricky cases.
What should you do is:
- for each number find the loop mod D (for example 2 mod 10 will be 2,4,8,6)
- for first number - D is in description, for second one D - is length of loop first number, for third D is length of loop second number and so on.

Some special cases when there are 1 in the middle of powers.
You shouldn't calculate more if you meet 1.
There are numbers when loop doesn't begin from first element of set. (!)

With best regards,
Pavel Ustinov

[helmet]

While I was sitting in class today I realised my error.

If anyone needs sample IO plz ask.

[Larry]

Ya, I also used rho's function, recursively. With N=10, it's not so difficult.

[howardcheng]

I missed a special case where the base is 0 mod m. Anyway, I used the euler phi function and then had to take care of the case when the base and m are not relatively prime using Chinese remaindering.

[abishek]

yes me too and i got AC.

the other approach is to try to find cycles in the a^i. though mathematically equivalent to phi function, it is easier to get that. but i got WA with that and i don't know why. can anybody tell me possible mistakes that i could have made in that?
bye
abi

[helmet]

the other approach is to try to find cycles in the a^i. though mathematically equivalent to phi function, it is easier to get that. but i got WA with that and i don't know why. can anybody tell me possible mistakes that i could have made in that?

Only mistake possible here is that you dont consider the case when the cycle doent start from the first position.It is just a simple recursion problem in this method.Other than that,I agree this is the easier method to code.

How come you you were able to compute the phi function so fast?I thought it would be slow.But I guess I am missing something.

[abishek]

once you have the prime factorisation of the number, computing the phi function is no problem. there is a formula

if n= p1^a1 . p2^a2 . .. pn^an

phi(n) = p1^(a1-1) . (p1-1) . p2^(a2-1) . (p2-1) ...

bye
abi

[helmet]

Phi(n)=n*(1-1/p1)*(1-1/p2)*... is a well known formula

However I wasnt aware that using the Chinese Remainder theorem we can get xmod(ab) given xmoda and xmodb.I know now.(where (a,b)=1).
Moreover since the mod limit is only 10000, prime generation is also easy and fast.I didnt realise this.

Thanks.

(btw did u get AC with cycles r u packed?)

[dll]

I got WA. anyone who got AC give some IO ? thanks

[helmet]

Some random IO ...

Input:

Code: Select all

9384 7 778 916 794 336 387 493 650
1422 3 28 691 60
7764 7 541 427 173 737 212 369 568
6430 3 531 863 124
4068 6 930 803 23 59 70 168
1394 7 12 43 230 374 422 920 785
8538 9 325 316 371 414 527 92 981 957 874
6863 1 997
7282 6 926 85 328 337 506 847
1730 4 858 125 896 583
546 5 368 435 365 44 751
1088 9 277 179 789 585 404 652 755 400 933
5061 7 369 740 13 227 587 95 540
796 1 435
379 8 602 98 903 318 493 653 757 302
281 7 442 866 690 445 620 441 730
8032 8 98 772 482 676 710 928 568 857
9498 4 587 966 307 684
6220 5 529 872 733 830 504
20 1 369
9709 6 341 150 797 724 619 246
2847 2 922 556
2380 9 765 229 842 351 194 501 35 765 125
4915 8 857 744 492 228 366 860 937 433
2552 8 229 276 408 475 122 859 396 30
1238 6 794 819 429 144 12 929
9530 7 405 444 764 614 539 607 841
2905 9 129 689 370 918 918 997 325 744 471
2184 1 500
9773 6 645 591 506 140 955 787
7670 3 543 465 198
9508 6 805 349 612 623 829 300
7344 7 569 341 423 312 811 606 802
5662 1 879
1306 1 737
9445 7 523 466 709 417 283 259 925
7638 3 625 601 37
3453 10 380 551 469 72 974 132 882 931 934 895
8661 4 200 982 900 997
2960 4 814 669 191 96
2927 7 85 341 91 685 377 543 937
9108 6 757 180 419 888 413 349
2173 10 10 337 211 343 588 207 302 714 373 322
1256 10 600 722 905 940 812 941 668 706 229 128
9151 5 659 921 225 423 270
1397 2 631 85
9293 3 673 851 626
5386 3 300 641 43
3899 4 299 191 525 591
8210 2 820 337
7733 6 995 5 380 770 274 777
8851 6 861 143 580 885 994 206
7622 8 505 614 962 755 327 260 945 203
3203 7 785 22 843 869 529 190 873
9909 9 499 37 809 754 249 304 334 134 649
2891 5 568 747 369 530 501
8047 9 798 250 991 304 34 364 498 254 893
7687 6 153 997 976 189 158 730
5437 1 415
3922 1 305
29 8 51 749 557 903 795 698 700 44
1040 3 429 404 501
682 8 539 160 152 536 135 340 693 216
6128 5 630 50 965 286 430
5344 6 178 901 239 972 950 290
5368 9 293 796 744 145 830 391 683 341 542
570 7 233 262 43 361 118 24 762
82 10 191 426 997 368 678 235 691 627 525 58
9615 9 206 359 313 387 101 347 727 995 917
6553 9 530 947 291 648 971 52 81 632 594
858 8 313 887 215 356 513 91 413 480
9611 10 190 275 356 642 621 434 988 889 339 567
7771 5 857 418 607 261 850
238 6 60 218 519 946 784 874
8459 4 638 290 484 608
479 8 315 472 730 101 460 619 439 26
1389 5 234 158 682 494 359
271 10 418 840 570 364 623 795 174 848 432 463
6683 1 293
5792 8 116 522 158 575 492 948 952 232
5022 8 741 55 31 99 326 82 517 517
3003 2 140 797
5405 9 581 219 22 971 863 813 380 978 686
1537 5 177 484 208 760 858
9745 10 912 128 951 237 561 819 106 564 50 245
8712 6 935 292 376 956 615 590
3769 4 919 806 883 823
6983 8 31 94 575 127 594 487 254 544
3075 5 714 180 378 763 776
7089 10 711 733 295 18 347 236 138 692 154 944
2574 9 926 292 711 19 218 837 964 56 91
3859 1 905
8572 2 634 686
4790 4 605 852 806 251
7869 4 486 7 196 640
2950 1 968
227 4 678 597 982 866
7561 7 956 771 519 212 343 533 197
2380 2 271 985
4173 8 235 41 284 73 399 831 64 348
#

OP:

Code: Select all

Case #1: 3928
Case #2: 28
Case #3: 7357
Case #4: 5951
Case #5: 3564
Case #6: 12
Case #7: 6679
Case #8: 997
Case #9: 5026
Case #10: 858
Case #11: 428
Case #12: 941
Case #13: 3630
Case #14: 435
Case #15: 251
Case #16: 279
Case #17: 5632
Case #18: 5497
Case #19: 3941
Case #20: 9
Case #21: 1
Case #22: 1
Case #23: 765
Case #24: 1586
Case #25: 2385
Case #26: 112
Case #27: 9085
Case #28: 129
Case #29: 500
Case #30: 8839
Case #31: 2313
Case #32: 7585
Case #33: 4361
Case #34: 879
Case #35: 737
Case #36: 6241
Case #37: 2437
Case #38: 1268
Case #39: 5974
Case #40: 1184
Case #41: 603
Case #42: 1189
Case #43: 16
Case #44: 472
Case #45: 8592
Case #46: 1266
Case #47: 5556
Case #48: 2540
Case #49: 633
Case #50: 820
Case #51: 7360
Case #52: 1485
Case #53: 1329
Case #54: 1034
Case #55: 1444
Case #56: 2815
Case #57: 7593
Case #58: 1346
Case #59: 415
Case #60: 305
Case #61: 28
Case #62: 481
Case #63: 583
Case #64: 2592
Case #65: 4704
Case #66: 1049
Case #67: 271
Case #68: 1
Case #69: 8216
Case #70: 6252
Case #71: 157
Case #72: 5153
Case #73: 4044
Case #74: 86
Case #75: 1177
Case #76: 338
Case #77: 531
Case #78: 1
Case #79: 293
Case #80: 544
Case #81: 3807
Case #82: 1421
Case #83: 581
Case #84: 152
Case #85: 5091
Case #86: 3025
Case #87: 1664
Case #88: 272
Case #89: 1026
Case #90: 6822
Case #91: 1576
Case #92: 905
Case #93: 3188
Case #94: 2485
Case #95: 1584
Case #96: 968
Case #97: 39
Case #98: 758
Case #99: 271
Case #100: 1054

Have fun! I know I did .

[dll]

thanks, helmet

[Minilek]

I understand how to solve this problem by looking for the order of the group generated by a^i mod m for each level up in the exponents. However, is there some number theory result that tells you the order of the group a (mod m), a^2 (mod m), ..., given a and m by doing less work? I see people have used the chinese remainder theorem and rho(?) function but I am not sure how to use these (or what the rho function is either). Can someone please guide me to something to read or please explain to me how this works?

I know if gcd(a,m) = 1, then a^{phi(m)+1} = a (mod m) and I see why also..but I do not know how to treat the case with gcd(a,m) > 2 other than looping through powers of a. Does a^{phi(m)+1} = a (mod m) hold true when gcd(a,m)>1 (minus the case where a is nilpotent i mean) ?

[I LIKE GN]

hello all...
basically i know little abot modular arithmetic...
so would u give me a relatively easy description to approach the prob.
i would like to know abot RHO' function and i can't get how phi
function is useful.
best regards.