洛谷P8348 「Wdoi-6」未知之花魅知之旅题解

题意：

称一个长度为 \(n\) 的正整数数列是「\(k\) - 好」的，当且仅当它满足以下条件：

对于 \(1< i< n\)，满足 \(a_{i-1},a_i,a_{i+1}\) 中最大的一个等于其他两个之和。

所有元素都不小于 \(k\)。

\(T\) 组询问，每次询问给定 \((a_0,a_1,x,y,k)\)，问是否存在「\(k\) - 好」数列（长度不小于 \(2\)），前两项为 \(a_0,a_1\) 并且有相邻两项依次为 \(x,y\) 。

输入格式：

第一行输入一个正整数 \(T\)，表示数据组数，对于每一组数据：

每行输入 \(5\) 个正整数，以空格隔开，分别为 \(a_0,a_1,x,y,k\)，含义如题目所述。

输出格式：

对于每一组数据，输出一行 yes 或 no，即是否存在一种可以使得神社变得美观的方法。

数据范围：

\(1 \leq \max(a_0,a_1,x,y,k) \leq 10^9,1 \leq T \leq 10^5\)。

很奇怪的一道题，我也说不太明白，简单讲一讲吧

首先有全用 \(a_{i + 1} = a_{i} + a_{i - 1}\) \[ x,\ y,\ x+y,\ x + 2y,\ 2x + 3y,\ 3x + 5y,\cdots, F_{n-1}x + F_{n-2}y \] 然后有用一次 \(a_{i + 1} = a_{i} + a_{i - 1}\) 再用两次 \(a_{i + 1} = |a_i - a_{i-1}|\) \[ F_{n-1}x + F_{n}y,\ F_{n}x + F_{n+1}y,\ F_{n-2}x + F_{n - 1}y,\ F_{n-1}x + F_{n}y \] 这种方法可以让它变回来。

考虑设 \(y = ax + b + k \ge x\) ，那么我们可以得到这样的数列 \[ x, a x+b+k,(a-1) x+b+k, x,(a-2) x+b+k, \cdots \] 然后发现这个过程很有规律，并且可以用辗转相除法来得到，就这样。

时间复杂度 \(\mathcal{O}(T \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

void work(int &a, int &b, int k)
{
    while(true)
    {
        if(a < b)
        {
            int d = (b - k) / a; if(!d) break;
            b -= d * a; if(d & 1) swap(a, b);
        }else if(a > b)
        {
            int d = (a - k) / b; if(!d) break;
            a -= d * b; if(d & 1) swap(a, b);
        }else break;
    }
}
bool check(int a, int b, int x, int y, int k)
{
    if(a < k || b < k || x < k || y < k) return false;
    work(a, b, k); work(x, y, k); return (a == x && b == y);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq;
    while(qwq--)
    {
        static int a0, a1, x, y, k;
        cin >> a0 >> a1 >> x >> y >> k;
        cout << (check(a0, a1, x, y, k) ? "yes" : "no") << '\n';
    }
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/article/a5ifhh16

[2] https://www.luogu.com.cn/article/1tk9lc4v

[3] https://www.luogu.com.cn/article/r5qhw6dy

题外话：

位于太平洋板块和亚欧板块消亡边界的日本，是世界上最多发地震的一个国家之一。2011 年 3 月 11 日，日本时间下午 2 时 46 分 18 秒，一场里氏 9 级的地震袭击了这个国家，随之而来的，是超过 10 米高的巨大海啸。妻离子散，家破人亡，是对这一悲剧性事件的最好描述。

2011 年 5 月，东方 Project 的创作者 ZUN，为地震中的灾民谱写了一张专辑，叫做《未知之花，魅知之旅》，所筹得的善款都被捐赠用于救灾赈灾之中。

而到了近未来的科学世纪，莲子和梅莉在一次聊天之中，又谈论到了这场大地震。这场地震对传统宗教的摧残程度也颇深，数千所神社不同程度遭受到了损毁，也有不少神社的主殿全毁或者半毁。甚至就连外界的博丽神社，也因此被摧毁。

莲子与梅莉决定动身，前往外界的博丽神社，进入幻想乡中，通报这一消息。