前言

鉴于keduoli姐已经写了A~E题的题解,故本文只写F题的题解.


Solution


求算方程的整数解

显然,我们需要先求解方程 + 的整数解().当该方程无解时,任意两个点之间都无法连边,存在无穷个连通块。求解方程的代码如下:

typedef long long ll;
typedef pair<ll, ll>pll;
typedef vector<pll> vpll;

vpll calc(ll R) {
    vpll v;
    for (ll x = 0;x * x <= R - x * x;x++) {
        ll t = R - x * x;
        ll p = round(sqrt(t));
        while (p * p < t) p++;
        while (p * p > t) p--;
        if (p * p == t) {
            v.push_back({ x,p });
        }
    }
    return v;
}

时间复杂度:


给定一个解求连通块个数

假如是方程的一个合法解,那么我们具有如下位移向量:

这些位移向量经过合成能够获得更加简洁的形式,下面直接给出结论:

记 g = gcd(u,v),那么

  1. u+v为奇数,简化形式为:.
  2. u+v为偶数,简化形式为:.

对于情况一,只要证明能够获得.

不失一般性,默认为奇数,为偶数.

方向上,要求 + 。根据裴蜀定理,该方程存在整数解.由于+ ,故在方向上,额外执行位移对总位移不存在影响.

注:位移方程的含义是:执行了位移和位移

方向上,我们需要执行|k1| + cv次v位移和|k2| + cu次u位移(c>=0).

根据既定条件,是奇数,既可以是奇数也可以是偶数。那么|k1| + cv 必定是奇数,|k2|+cu即可以是奇数,也可以是偶数.通过调整c值,我们能够控制|k2|+cu为偶数.与此同时,当c是无穷大时,操作次数也是无穷大的.

对于v位移,我们先执行u次-v位移,剩余偶数次操作,我们执行v,-v v,-v,v,-v....;

对于u位移,我们先执行v次 u位移,剩余偶数次操作,我们执行u,-u,u,-u,u,-u....

那么在方向上的位移总和为,u*(-v) + 0 + v*u + 0 = 0.

证明完毕!


对于情况二,需要分类讨论,能够证明无法获得,然而可获得.

均为奇数时,执行位移和位移.

方向上,要求 + .

显然,为奇数,一奇一偶.默认为奇数,为偶数.

方向上,依旧执行p1 = |k1|+cv次v位移和p2 = |k2|+cu次u位移.显然,p1和p2一奇一偶.默认p1为奇数,p2为偶数

对于v位移,我们依旧先执行u次-v位移,剩余偶数次操作,我们执行v,-v,v,-v,v,-v....位移操作.

对于u位移,位移量的总和无法等于 v*u,因为我们先执行 v次u位移后,剩余奇数次u位移操作,奇数次操作无法相互抵消.

因此,在方向上的位移量为的情况下,方向上的位移量无法等于0.然而能够证明,方向上的位移量允许为.


当u,v均为偶数时,我们需要对问题做一些转化.即,显然均为奇数.

方向上,要求 + 等价于 + .

问题转化后,此情况和均为奇数的情况是等价的. 也能证明,在方向上的位移量为的情况下,方向上的位移量无法等于0.然而能够证明,方向上的位移量允许为.

证明完毕


对于情况一,连通块的总数为.

选择如下点作为位移的起点,便能位移到平面上的任意一个点。

对于情况二,连通块的总数为.

选择如下点作为位移的起点,便能位移到平面上的任意一个点。


Code

注:部分代码参考了牛客周赛讲解.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll>pll;
typedef vector<pll> vpll;

vpll calc(ll R) {
    vpll v;
    for (ll x = 0;x * x <= R - x * x;x++) {
        ll t = R - x * x;
        ll p = round(sqrt(t));
        while (p * p < t) p++;
        while (p * p > t) p--;
        if (p * p == t) {
            v.push_back({ x,p });
        }
    }
    return v;
}

ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        ll R;
        cin >> R;
        auto v = calc(R);
        if (v.size() == 0) {
            cout << "inf\n";
            continue;
        }
        
        ll gg = 0;
        for(auto u:v){
            ll x = u.first,y = u.second;
            gg = gcd(gg,gcd(x*x+y*y,2ll*y*y));
        }
        
        cout<<gg<<'\n';
    }
    return 0;
}

写在最后

笔者能力有限,推导F题花了本人整整一天的时间。倘若讲解有不恰当的地方,请多多见谅。菜,求放过!