NOIP2005普及组第4题 循环
NOIP2005普及組第4題 循環
時間限制:?1 Sec??內存限制:?128 MB
提交:?27??解決:?6
[提交][狀態][討論版][命題人:外部導入]
題目描述
樂樂是一個聰明而又勤奮好學的孩子。他總喜歡探求事物的規律。一天，他突然對數的正整數次冪產生了興趣。
?
眾所周知，2的正整數次冪最后一位數總是不斷的在重復2，4，8，6，2，4，8，6……我們說2的正整數次冪最后一位的循環長度是4（實際上4的倍數都可以說是循環長度，但我們只考慮最小的循環長度）。類似的，其余的數字的正整數次冪最后一位數也有類似的循環現象：
循環
循環長度
?
| 數字 | 循環 | 循環長度 |
| 2 | 2、4、8、6 | 4 |
| 3 | 3、9、7、1 | 4 |
| 4 | 4、6 | 2 |
| 5 | 5 | 1 |
| 6 | 6 | 1 |
| 7 | 7、9、3、1 | 4 |
| 8 | 8、4、2、6 | 4 |
| 9 | 9、1 | 2 |
這時樂樂的問題就出來了：是不是只有最后一位才有這樣的循環呢？對于一個整數n的正整數次冪來說，它的后k位是否會發生循環？如果循環的話，循環長度是多少呢？
注意：
1．?如果n的某個正整數次冪的位數不足k，那么不足的高位看做是0。
2．?如果循環長度是L，那么說明對于任意的正整數a，n的a次冪和a?+?L次冪的最后k位都相同。
輸入
????? 只有一行，包含兩個整數n（1?<=?n?<?10100）和k（1?<=?k?<=?100），n和k之間用一個空格隔開，表示要求n的正整數次冪的最后k位的循環長度。
輸出
??? 包括一行，這一行只包含一個整數，表示循環長度。如果循環不存在，輸出-1。
?
?
【數據規模】
?
?
?
對于30%的數據，k?<=?4；
?
對于全部的數據，k?<=?100。
?
樣例輸入
32 2
樣例輸出
4 提示
?
題目類型：高精度乘法+規律。
?
分析：一般來說遇到這種問題，像10^100這樣的數據范圍，不是高精度就是另有規律可循。這是一個循環結問題，以往有遇到打表找規律的這種問題，極容易被忽悠。
?
WA點：
- 答案有可能存在long long int保存不下的情況，需要用數組保存。并且過程需要高精度高乘。
- 既需要高精度低乘，又需要高精度高乘，在數組拷貝的過程中極可能出現失誤。
- 單組輸入
?
TLE點：
- 在數組的比較過程中，可以用O(1)的時間復雜度解決，而不必O(100)。
?
高精度高乘：大數與大數相乘，數組乘數組實現。
?
高精度低乘：大數與整數（較小）相乘，數字乘數字實現。
?
規律：當后K為數字存在循環結的必要條件是，后K-1位數字存在循環結，并且K的最小循環結必定是K-1的最小循環結的整數倍。并且對于當前位數的處理不必要取模，既然已經用了數組高精度保存便可以只考慮當前位數。在比較時，顯然后K-1位已經按照之前的循環結遞推過來必定相同，我們只需要比較倒數第K位是否相等即可。
?
技巧：關于查找循環結上限的問題，當前位數出現可能是0,1,2,3,4,5,6,7,8,9，在10次之內必定會出現與第一次相同的情況，當前次數*K-1的循環結即可得到K的循環結。如果10之內未能出現，那肯定就不存在了。
?
?
解析：我直接舉一個例子進行說明吧：111 3（由于1的循環長度就是1，所以我直接從末兩位循環開始）
?
? ? ? ? ? 我們來看111的末兩位循環：
?
? ? ? ? ? 111 ?-> 321 -> 631 -> 041 -> 551 -> 161 -> 871 -> 681 -> 591 -> 601 -> 711?
?
? ? ? ? ? 711處末兩位出現循環，循環長度為10，循環節為11-> ...-> 01
?
? ? ? ? ??現在我們再來看末三位循環：
?
? ? ? ? ? 111->...->601 (10個數)
?
? ? ? ? ? 711->...->201 (201就是601^2的末三位)
?
? ? ? ? ? 311->...->801 (801就是601^3的末三位)
?
? ? ? ? ? 911->...->401 (401就是601^4的末三位)
?
? ? ? ? ? 511->...->001 (001就是601^5的末三位)
?
? ? ? ? ? 111->...->601 (601就是601^6的末三位) ?
?
? ? ? ? ? 末三位的循環長度就是5*10=50；
?
?
?
? ? ? ? ? 好了，現在來講具體的做法，并假設我們現在求數字n的后k位循環。
?
? ? ? ? ? 樸素的做法就是直接求n^2,n^3,n^4.。。。，并判斷是否出現循環。但觀察上面的演示例子，我們發現可以不必這樣，以n=111為例，末兩位循環節長度為10，即表示n與（n^10）*n的末兩位是相同的。對于末三位的循環，肯定是（m*n^10），即m*(n^10)與n^10的末三位是相同的，m*（n^10）*n的末三位與n相同。?于是，計算末三位循環的時候，我們就直接將n^10作為第一個數，然后每次乘n^10，共乘5次，末三位出現循環，即m=5，所以末三位循環街長度就為5*10=50。
?
#include<iostream> #include<cstring> #include<cstdio> #include<string> #include<algorithm> using namespace std; string s; int m, k; int i, j; int a[205], aans[205], n[205], ans[205], last[205], now[205], t[205]; int single_j[12] = { 1,1,4,4,2,1,1,4,4,2 };//單循環結 void init() {memset(a, 0, sizeof a); memset(last, 0, sizeof last);memset(aans, 0, sizeof aans); memset(now, 0, sizeof now);memset(ans, 0, sizeof ans); memset(n, 0, sizeof n); memset(t, 0, sizeof t);//for (int i = 1;; i++) { if (m == 0) break; n[i] = m % 10; m /= 10; }//將m存入數組n，以便于高精度 } void multiplyh(int x[], int y[], int z[]) {//高精度高乘int up = 0;for (int ii = 1; ii <= k; ii++) {for (j = 1; j <= k; j++){z[ii + j - 1] += (x[j] * y[ii] + up) % 10;up = (x[j] * y[ii] + up) / 10;}up = 0;}for (int ii = 1; ii <= k; ii++) {//進位z[ii + 1] += z[ii] / 10;z[ii] %= 10;} } void multiplyl(int x[], int yy, int z[]) {//高精度低乘int up = 0;for (int ii = 1; ii <= k; ii++) {z[ii] = (x[ii] * yy + up) % 10;up = (x[ii] * yy + up) / 10;} } int main() {//scanf("%d%d", &m, &k); init();cin >> s;cin >> k;int temp = 0, len = s.size();for (i = len - 1; i >= len - k; i--)n[++temp] = s[i] - '0';int tmp = 0;for (int i = 1; i <= k; i++) ans[i] = n[i];for (int i = 1; i < single_j[n[1]]; i++) {memset(aans, 0, sizeof aans);multiplyh(ans, n, aans);for (int j = 1; j <= k; j++) { ans[j] = aans[j]; }//更新為第一次出現末尾循環節的狀態 }t[1] = single_j[n[1]];//最低位的循環結for (int i = 1; i <= k; i++) now[i] = ans[i];int pos = 2;//當前倒數位數while (pos <= k) {for (int j = 1; j <= k; j++) {ans[j] = n[j];last[j] = now[j];}tmp = 0;while (tmp < 11){tmp++;memset(aans, 0, sizeof aans);multiplyh(ans, now, aans);for (j = 1; j <= k; j++) {ans[j] = aans[j];}if (ans[pos] == n[pos]) break;//找到循環結memset(aans, 0, sizeof(aans));multiplyh(last, now, aans);//更新lastfor (j = 1; j <= k; j++) last[j] = aans[j];}if (tmp >= 11) { cout << -1; return 0; }for (int j = 1; j <= k; j++) now[j] = last[j];memset(aans, 0, sizeof aans);multiplyl(t, tmp, aans);//更新循環節數組for (int i = 1; i <= 100; i++) t[i] = aans[i];pos++;}int flag = 0;//不輸出前導0for (int i = 100; i >= 1; i--) {if (t[i]) flag = 1;if (flag) cout << t[i];}return 0; }
?
轉載于:https://www.cnblogs.com/caiyishuai/p/8585886.html
總結
以上是生活随笔為你收集整理的NOIP2005普及组第4题 循环的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： iOS Webview打开不受信的UR
- 下一篇： 火材人是谁画的呢？