杭电ACM第1005题，自己测试使用结果都是对的，但是提交后提示Runtime Error (ACCESS_VIOLATION)

发布网友发布时间：2022-04-24 13:56

共2个回答

热心网友时间：2023-10-15 08:48

这题可以用二分求幂来做的。
构造一个矩阵每次都是一个矩阵的转移。然后可以用二分。
当然也是有周期的。最大的周期是49
因为这些数字都是要7的范围内
如果有两个数字连续一样的话，后面的数字就会和前面重复
f[i]==f[i+k]&&f[i+1]==f[i+1+k]
这样的话后面就会重复的
//此题是一个很典型的递归mod找周期的题目，很值得研究！
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 50; //mod7 2个数循环节不会超过49
int f[maxn];
int main()
{
int a, b, n, i;
while (scanf("%d%d%d",&a,&b,&n) != EOF )
{
if (a+b+n == 0)break;
f[1] = 1;
f[2] = 1;

for (i = 3; i < 50; i++)
{
f[i] = (a*f[i-1]+b*f[i-2]) % 7;
if (f[i] == 1 && f[i-1] == 1)break; //可能对于不同的A, B 每次的周期会不一样
}
i -= 2; //找周期
n %= i;
if (n == 0)n = i;
cout<<f[n]<<endl;
}
return 0;
}

热心网友时间：2023-10-15 08:49

这个题你想得容易了，当数比较大的时候你这种算法会超时的，我以前用c写过这个代码,已经ac了：你可以参考下：
#include <stdio.h>
int main()
{
int a, b, n;
int f[51], i, t;
f[0] = f[1] = 1;
while (scanf("%d%d%d", &a, &b, &n) != EOF && (a || b || n))
{
for (i = 2; i < 51; i++)
{
f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
}
for (i = 0; i < 49; i++)
{
if (f[49] == f[i] && f[50] == f[i + 1])
{
t = i;
break;
}
}
printf("%d\n", f[n % 49 + t - 2]);
}
return 0;
}追问能简单解释下您的算法嘛麻烦鸟~