UVa 10692 - Huge Mods
Published on 2016-03-02描述
给定 ，以及 ，请你计算：
计算的顺序是从上往下，即 。
样例输入
10 4 2 3 4 5 100 2 5 2 53 3 2 3 2 #
样例输出
Case #1: 2 Case #2: 25 Case #3: 35
分析
在我的 模运算总结 中提到了指数循环节的事情：
此公式没有 的要求，但再次声明一下，只有 时此公式成立，所以千万不要盲目的取余了再加！！！网上的有些程序明显是错的，只不过 UVa 的数据太弱没被搞掉而已。
既然有了这个公式，我们就可以先预处理出所有 ，然后递归解决即可，由于只有 时此公式成立，所以再快速幂的时候先试乘，如果不超直接返回结果，否则返回取余再加的结果。
最后答案输出的时候还要对 取一次模，因为答案并不做谁的指数，也就没有这个公式了。
代码
// Created by Sengxian on 3/1/16. // Copyright (c) 2016年 Sengxian. All rights reserved. // UVa 10692 指数循环节 #include <algorithm> #include <iostream> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <vector> using namespace std; inline int ReadInt() { int n = 0, ch = getchar(); while(!isdigit(ch) && ch != '#') ch = getchar(); if(ch == '#') exit(0); while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar(); return n; } typedef long long ll; const int maxm = 10000 + 3, maxn = 10 + 3; int phi[maxm]; void process() { memset(phi, 0, sizeof(phi)); phi[1] = 1; for(int i = 2; i < maxm; ++i) if(!phi[i]) for(int j = i; j < maxm; j += i) { if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } ll mod_pow(ll a, ll b, ll MOD) { ll ans = 1; for(int i = 0; i < b; ++i) { ans *= a; if(ans > MOD) break; if(i + 1 == b) return ans; } ans = 1; while(b > 0) { if(b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans + MOD; } int m, n, a[maxn]; //[idx, n) ll f(ll idx, ll MOD) { if(idx == n - 1) return a[idx] < MOD ? a[idx] : a[idx] % MOD + MOD; return mod_pow(a[idx], f(idx + 1, phi[MOD]), MOD); } int main() { process(); int caseNum = 0; while(m = ReadInt(), n = ReadInt(), m + n) { for(int i = 0; i < n; ++i) a[i] = ReadInt(); printf("Case #%d: %lld\n", ++caseNum, f(0, m) % m); } return 0; }
附加输入
1000 3 12 1 1 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 #
附加输出
Case #1: 12 Case #2: 3928 Case #3: 28 Case #4: 7357 Case #5: 5951 Case #6: 3564 Case #7: 12 Case #8: 6679 Case #9: 997 Case #10: 5026 Case #11: 858 Case #12: 428 Case #13: 941 Case #14: 3630 Case #15: 435 Case #16: 251 Case #17: 279 Case #18: 5632 Case #19: 5497 Case #20: 3941 Case #21: 9 Case #22: 1 Case #23: 1 Case #24: 765 Case #25: 1586 Case #26: 2385 Case #27: 112 Case #28: 9085 Case #29: 129 Case #30: 500 Case #31: 8839 Case #32: 2313 Case #33: 7585 Case #34: 4361 Case #35: 879 Case #36: 737 Case #37: 6241 Case #38: 2437 Case #39: 1268 Case #40: 5974 Case #41: 1184 Case #42: 603 Case #43: 1189 Case #44: 16 Case #45: 472 Case #46: 8592 Case #47: 1266 Case #48: 5556 Case #49: 2540 Case #50: 633 Case #51: 820 Case #52: 7360 Case #53: 1485 Case #54: 1329 Case #55: 1034 Case #56: 1444 Case #57: 2815 Case #58: 7593 Case #59: 1346 Case #60: 415 Case #61: 305 Case #62: 28 Case #63: 481 Case #64: 583 Case #65: 2592 Case #66: 4704 Case #67: 1049 Case #68: 271 Case #69: 1 Case #70: 8216 Case #71: 6252 Case #72: 157 Case #73: 5153 Case #74: 4044 Case #75: 86 Case #76: 1177 Case #77: 338 Case #78: 531 Case #79: 1 Case #80: 293 Case #81: 544 Case #82: 3807 Case #83: 1421 Case #84: 581 Case #85: 152 Case #86: 5091 Case #87: 3025 Case #88: 1664 Case #89: 272 Case #90: 1026 Case #91: 6822 Case #92: 1576 Case #93: 905 Case #94: 3188 Case #95: 2485 Case #96: 1584 Case #97: 968 Case #98: 39 Case #99: 758 Case #100: 271 Case #101: 1054
