NOI2018模拟赛(十) Problem C:gcd

题目描述

有[latex]Q[/latex]组询问,每组给出[latex]A,B[/latex],求[latex]1\le x\le A,1\le y\le B[/latex],[latex]f(x,y)[/latex]的最大值,并输出取到最大值的有序对[latex](x,y)[/latex]的个数。

[latex]f[/latex]的计算规则如下

1.[latex]f(a,b)=f(b,a),(b>a)[/latex]

2.[latex]f(a,0)=0[/latex]

3.[latex]f(a,b)=f(b,a\bmod b)[/latex]

题解

题目写的这么神,那我们考虑乱搞。

首先有个常识,辗转相除在两个斐波那契数之间会取到最大次数。

然后写个暴力,把小范围内的所有有序对的答案都算出来。

题目给出了两个限制,就相当于在算出来的那个矩阵上从左上角切一个[latex]A\times B[/latex]的矩形,求里面的最大值和最大值的个数,显然横竖没有影响。

那我们就可以把所有对答案可能有贡献的地方打印出来(也就是打印出以[latex](x,y)[/latex]为右下角的矩形里面[latex](x,y)[/latex]取到最大值的点)。

然后发现无论打印最大值为几的图,大致都和下面这个差不多。

图上大致是有几行几列的点,然后还有两个特殊的点,而且每行每列还呈现周期性变化。

那么把特殊点的坐标和每列第一个点的坐标写下来。

答案 2 3 4 5 6
special (4,3) (7,5) (11,8) (18,13) (29,21)
normal (3,2) (5,3);(7,4) (8,5);(11,7);(12,7) (13,8);(18,11);(19,11);(19,12) (21,13);(29,18);(30,19);(31,18);(31,19)

嗯,写不下了。

special的点横纵坐标竟然都是线性递推的关系,每一个答案normal的点竟然都是由上一行个答案所有的点演变而来[latex](x,y)\rightarrow (x+y,y)[/latex]。

没了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int x; scanf("%lld", &x); return x;
}
#define xx first
#define yy second
#define pb push_back
typedef pair<int, int> pir;
const int mod = 1000000007;

vector<pir> f, s[100];
int fib[100];
int find(int a, int b) {
	int ka = upper_bound(fib + 1, fib + 91, a) - fib;
	int kb = upper_bound(fib + 1, fib + 91, b) - fib;
	if (ka > kb + 1) ka = kb + 1;
	if (ka == kb) kb--;
	return kb - 1;
}

signed main() {
    f.pb(pir(1, 1));
    f.pb(pir(3, 2));
    f.pb(pir(4, 3));
    s[2].pb(pir(3, 2));
    for (int i = 3; i <= 90; i++) {
        f.pb(pir(f[i - 1].xx + f[i - 2].xx, f[i - 1].yy + f[i - 2].yy));
        for (int j = 0; j < i - 2; j++) {
            s[i].push_back(pir(s[i - 1][j].xx + s[i - 1][j].yy, s[i - 1][j].xx));
        }
        s[i].pb(pir(f[i - 1].xx + f[i - 1].yy, f[i - 1].xx));
    }
    fib[0] = fib[1] = 1;
    for (int i = 2; i <= 90; i++)
    	fib[i] = fib[i - 1] + fib[i - 2];
    	
    int Q = read();
    while (Q--) {
    	int A = read(), B = read(), ans = 0;
		if (A < B) swap(A, B);
		if (B == 1) { printf("1 %lld\n", A % mod); continue; }
		if (A == 2 && B == 2) { puts("1 4"); continue; }
    	int k = find(A, B);
    	printf("%lld ", k);
    	for (int i = 0, _ = s[k].size(); i < _; i++) {
    		int x = s[k][i].xx, y = s[k][i].yy;
    		if (y <= B && x <= A) {
    			ans = (ans + (A - x) / y + 1) % mod;
    		}
    		if (y <= A && x <= B) {
    			ans = (ans + (B - x) / y + 1) % mod;
    		}
    	}
    	if (f[k].xx <= A && f[k].yy <= B)
    		ans = (ans + 1) % mod;
    	if (f[k].xx <= B && f[k].yy <= A)
    		ans = (ans + 1) % mod;
    	printf("%lld\n", ans);
    }
}

还有神奇的正解,其实最后的代码差不多。

设[latex]f(a,b)[/latex]表示欧几里得步数。

我们先设斐波那契数[latex]F_0=1,F_1=1,F_{i+2}=F_{i+1}+F_i[/latex]
容易发现[latex]f(F_k,F_{k+1})=k[/latex]。

结论一:如果[latex]f(x,y)=k[/latex],且[latex]y>x[/latex],则一定有[latex]x\ge F_k[/latex]以及[latex]y>=F_{k+1}[/latex]。
这个可以用归纳法证明。

然后我们发现,对于[latex]gcd(x,y)>1[/latex]如果[latex]f(x,y)>1[/latex]这样的[latex](x,y)[/latex]不会计算入答案。
这个也好证。

于是我们只需要在答案等于[latex]1[/latex]的时候特判,其余情况当然只需要考虑[latex]\gcd[/latex]为[latex]1[/latex]的点对。

我们定义如果不存在[latex]x_1 < x[/latex]和[latex]y_1 < y[/latex]使得[latex]f(x_1,y_1) > f(x,y)[/latex]那么[latex](x,y)[/latex]是好的。
显然我们只统计好的点对。

然后我们定义如果[latex]f(x,y)=k[/latex]且[latex]x,y\le F_{k+2}+F_{k−1}[/latex]那么[latex](x,y)[/latex]是优秀的。

结论二:如果[latex](x,y)[/latex]是好的,那么一步后会变成优秀的。
可以用反证法证明。

然后我们只需要找出所有优秀的点对,就很容易统计答案。
找的方法是用[latex]k[/latex]的得到[latex]k+1[/latex]的。

优秀的点对有多少呢?
在最小的情况下是[latex](F_k,F_{k+1})[/latex],容易发现它只会产生[latex]2-3[/latex]个新的,而其余的则只能产生[latex]1[/latex]个。
因此是[latex]log[/latex]级别的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注