题解：P14308 【MX-S8-T1】斐波那契螺旋

细数繁星 · 2025-10-25 18:35:46 · 题解

询问值小于等于 10^{18}，数量级在 f_{90} 附近。而每个正方形的起始结点，终止结点都可以推导。T 最大在 10^6，加输入输出优化，每次查询遍历预处理好的正方形信息，符合条件输出，可以通过此题。

推导方法：对 (i-2)\bmod 4 进行分类讨论。这些是易得的，代码中 (fx,fy) 是正方形左下角的坐标，(tx,ty) 是正方形右上角的坐标，f_i 即为边长。实现逻辑也很简单，不再过多阐述。

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {

}

struct Rectangle {
    ll fx, fy, tx, ty;
}fib[101];

main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fib[1] = {-1, 0, 0, 1};
    fib[2] = {-1, -1, 0, 0};
    rep(i, 3, 92) {
        if ((i - 2) % 4 == 1) {
            fib[i].ty = fib[i - 2].ty;
            fib[i].fx = fib[i - 1].tx;
            fib[i].fy = fib[i - 1].fy;
            fib[i].tx = fib[i].fx + fib[i].ty - fib[i].fy;
        }
        if ((i - 2) % 4 == 2) {
            fib[i].fx = fib[i - 2].fx;
            fib[i].fy = fib[i - 1].ty;
            fib[i].tx = fib[i - 1].tx;
            fib[i].ty = fib[i].fy + fib[i].tx - fib[i].fx;
        }
        if ((i - 2) % 4 == 3) {
            fib[i].fy = fib[i - 2].fy;
            fib[i].tx = fib[i - 1].fx;
            fib[i].ty = fib[i - 1].ty;
            fib[i].fx = fib[i].tx - (fib[i].ty - fib[i].fy);
        }
        if ((i - 2) % 4 == 0) {
            fib[i].fx = fib[i - 1].fx;
            fib[i].tx = fib[i - 2].tx;
            fib[i].ty = fib[i - 1].fy;
            fib[i].fy = fib[i].ty - (fib[i].tx - fib[i].fx);
        }
    }
    int T;
    cin >> T;
    while (T--) {
        ll x, y;
        cin >> x >> y;
        rep(i, 1, 92) {
            if (fib[i].fx <= x && x <= fib[i].tx && fib[i].fy <= y && y <= fib[i].ty) {
                ll ans = fib[i].tx - fib[i].fx;
                cout << ans << '\n';
                break;
            }
        }
    }
//  int t; cin >> t; while (t--) solve();
    return 0;
}