题解：CF2231F Quadratic Jumps

· · 题解

简单题，完全够不上2600和紫。

思路：

首先有个很经典东西叫四平方和定理，就是说一个正整数肯定能被拆成不超过四个完全平方数之和，答案的上界就压下来了。

考虑到还有跳出 [a,b] 又跳回来的情况，需要判断是否有可能跳两步或三步的情况。

跳过去又跳回来是有可能跳出 [1,n] 的范围的，所以我们预处理出 x 和 y 数组，满足 y_i^2-x_i^2=i，且 y_i 和 x_i 最小。

套一个平方差公式，变成 (y_i-x_i)(y_i+x_i)=i，易得 y_i-x_i 最大时 y_i 和 x_i 最小。

如此便可预处理出左右横跳两步是否会超出区间。

具体来说就是 a 两步跳到 b 可以是 a 到 a\pm y_{b-a}^2，再到 a\pm y_{b-a}^2\mp x_{b-a}^2，也就是 b，然后判断 a\pm y_{b-a}^2 是否超出边界即可。

这样我们就可以 O(1) 求出答案是否可能为 2。

答案为 3 可以枚举第一步从 a 跳至 a\pm x^2，再判断 a\pm x^2 是否可两步跳至 b，时间复杂度 O(\sqrt n)。

总复杂度为 O((n+q)\sqrt n)。

代码：

//你全家都是网珺淏
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rop(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define por(i,a,b) for(int i=a;i>b;i--)
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double ld;
using namespace std;
int t,n,q,dp[200005],sq[200005],x[200005],y[200005],a,b;
bool check2(int a,int b){
    if(a>b)
        swap(a,b);
    if(dp[b-a]<=2)
        return 1;
    if(!x[b-a])
        return 0;
    if(a+y[b-a]*y[b-a]<=n||b-y[b-a]*y[b-a]>=1)
        return 1;
    return 0;
}
bool check3(int a,int b){
    rep(x,1,447){
        if(a+x*x<=n)
            if(check2(a+x*x,b))
                return 1;
        if(a-x*x>=1)
            if(check2(a-x*x,b))
                return 1;
    }
    return 0;
} 
void solve(){
    cin>>n>>q;
    while(q--){
        cin>>a>>b;
        int ans=dp[b-a];
        if(check2(a,b))
            ans=min(ans,2ll);
        if(check3(a,b))
            ans=min(ans,3ll);
        cout<<ans<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    dp[0]=0;
    rep(i,1,447)
        sq[i*i]=i;
    rep(i,1,200000)
        if(!sq[i])
            sq[i]=sq[i-1];
    rep(i,1,200000){
        dp[i]=4;
        for(int j=1;j*j<=i;j++){
            dp[i]=min(dp[i],dp[i-j*j]+1);
            if(i%j||(i/j-j)&1)
                continue;
            x[i]=i/j-j>>1;
            y[i]=i/j+j>>1;
        }
    }
    while(t--)
        solve();
    return 0;
}
/*
？现在jc方式那么低级啊
*/