[雅礼1706 Day 8] gcd

定义 为使用辗转相除法计算 和 的最大公约数需要的步数: 个询问: 求 , 并求出有多少对 取到最大值, 模 .

感谢 Skipher 神犇教我找规律......就算对本质一无所知, 也是有办法 AC 的. Orz

不妨设 .

特判. 其余情况, 第一问的答案是满足

的最大的 . 是斐波纳契数列的第 项, .

递归次数取到最大值这个结论我是在 <算导> 里看到的, 也可以打表观察出来.

第二问. 把所有 的点打出来没有什么帮助. 只看对答案可能有贡献的点: 打表的代码在最后.

发现: 1. 点关于 y = x 对称 2. k = 1 的情况比较特殊, 考虑特判 2. k > 1, 有一对奇怪的点 (用黄色圈了起来) 3. 正常的点具有周期性; 对于 x > y 的点, 周期 = y 坐标

下面只考虑 x > y.

把奇怪的点的坐标, 和正常的那些每一列的第一个点打出来 (由周期性可以推算其他点的坐标):

k	奇怪	正常
2	(4,3)	(3,2)
3	(7,5)	(5,3) (7,4)
4	(11,8)	(8,5) (11,7) (12,7)
5	(18,13)	(13,8) (18,11) (19,11) (19,12)
6	(29,21)	(21,13) (29,18) (30,19) (31,18) (31,19)

对于奇怪的点, y 坐标是斐波纳契数, x 坐标也有和斐波纳契数列一样的递推关系.

对于正常的点, 我们发现它们均是由上一排所有点经过 (x,y) -> (x+y,x) 的变换得到的.

由于斐波纳契数的增长是指数级的, k 不会很大. 实验表明不超过90.

先打出斐波纳契数表, 和上面的表格.

对于每个询问, 求出 k, 然后利用上面的表格以及周期性和对称性计算第二问的答案.

打表的程序:

typedef long long ll;

const int N = 51, M = 51, MOD = 1e9 + 7;

int f[N][N], cnt[M][N][N], mx[N][N];
bool vis[N][N];

int F(int i, int j)
{
	if (j == 0) return 0;
	if (vis[i][j]) return f[i][j];
	vis[i][j] = true;
	return f[i][j] = F(j, i%j) + (i >= j);
}

int main()
{
	rep (i, 1, N) rep (j, 1, N) if (!vis[i][j]) F(i, j);
	rep (i, 1, N) rep (j, 1, N) mx[i][j] = max(f[i][j], max(mx[i-1][j], mx[i][j-1]));

	rep (k, 1, 7)
	{
		printf("k = %d\n", k);
		rep (i, 1, N)
		{
			rep (j, 1, N)
				putchar(f[i][j] == k && k == mx[i][j] ? '*' : ' '), putchar(' ');
			putchar('\n');
		}
		putchar('\n');
	}
	return 0;
}