題目鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=1005
?
Number Sequence
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 85249????Accepted Submission(s): 20209
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
?
?
?
?
?
?
解析：
這是一道尋找循環點的問題，可能很多人在杭電上通過了這個題目，但是我建議大家將自己的代碼再貼到另一個OJ上進行測試 http://zju.acmclub.com/index.php?app=problem_title&id=1&problem_id=2603 。
很多人都認為周期是49，但是給出的解題報告都不是很有說服力。
所以，我們可以尋找循環的開頭以及周期，然后輸出，這樣能夠保證正確性，當然一開始的記錄數組最好能夠相對大一些，不然仍然不能通過測試。
代碼：
?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define swap(a,b) {(a)=(a)^(b); (b)=(a)^(b); (a)=(a)^(b);}
#define MAXN 65535
#define INF 1e9
int f[1200];
int main(){
int a,b,n;
int i, j;
int flag, term, temp, begin;
while(~scanf("%d%d%d", &a, &b, &n), (a||b||n)){
memset(f, 0, sizeof(f));
f[1]=1;
f[2]=1;
term = n;
flag = 0;
for(i=3; i<=n&&!flag; i++){
f[i] = (a*f[i-1]+b*f[i-2])%7;
for(j = 2; j<i; j++){
if(f[i]==f[j]&&f[i-1]==f[j-1]){
term = i-j;
begin = j-2;
flag = 1;
break;
}
}
}
if(flag)
printf("%d\n", f[begin+(n-1-begin)%term+1]);
else
printf("%d\n", f[n]);
}
return 0;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
