牛客周赛 Round 50题解

前言

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

Solution

求算方程的整数解

显然，我们需要先求解方程 $u^2$ + $v^2 = R$ 的整数解( $u,v \ge0$ ).当该方程无解时，任意两个点之间都无法连边，存在无穷个连通块。求解方程的代码如下：

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;
}

时间复杂度： $O(\sqrt{R})$

给定一个解求连通块个数

假如 $(u,v)$ 是方程的一个合法解，那么我们具有如下位移向量：

$(u,v),(u,-v),(-u,v),(-u,-v),(v,u),(v,-u),(-v,u),(-v,-u)$

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

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

u+v为奇数，简化形式为： $(\pm g,0),(0,\pm g)$ .
u+v为偶数，简化形式为： $(\pm g, \pm g)$ .

对于情况一，只要证明能够获得 $(g,0)$ .

不失一般性，默认 $u$ 为奇数， $v$ 为偶数.

在 $X$ 方向上，要求 $k_{1}*u$ + $k_{2}*v = g$ 。根据裴蜀定理，该方程存在整数解 $(k_1,k_2)$ .由于 $-v*u$ + $u*v = 0$ ，故在 $X$ 方向上，额外执行 $v$ 次 $(\pm u, \pm v)$ 和 $u$ 次 $(\pm v,\pm u)$ 位移对总位移不存在影响.

注：位移方程的含义是：执行了 $|k_1|$ 次 $(\pm u, \pm v)$ 位移和 $|k_2|$ 次 $(\pm v,\pm u)$ 位移

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

根据既定条件， $g$ 和 $k_1$ 是奇数， $k2$ 既可以是奇数也可以是偶数。那么|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....

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

证明完毕！

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

当 $u,v$ 均为奇数时，执行 $|k_1|$ 次 $(\pm u, \pm v)$ 位移和 $|k_2|$ 次 $(\pm v,\pm u)$ 位移.

在 $X$ 方向上，要求 $k_{1}*u$ + $k_{2}*v = g$ .

显然， $g,u,v$ 为奇数， $k_1,k_2$ 一奇一偶.默认 $k_1$ 为奇数， $k_2$ 为偶数.

在 $Y$ 方向上，依旧执行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位移操作，奇数次操作无法相互抵消.

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

当u,v均为偶数时，我们需要对问题做一些转化.即 $u = c_{1}*g,v = c_{2}*g$ ，显然 $c_{1},c_{2}$ 均为奇数.

在 $X$ 方向上，要求 $k_{1}*u$ + $k_{2}*v = g$ 等价于 $k_{1}*c_{1}$ + $k_{2}*c_{2} = 1$ .

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

证明完毕

对于情况一，连通块的总数为 $g^2$ .

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

$(0,0),...,(0,g-1),...(g-1,0),...,(g-1,g-1)$

对于情况二，连通块的总数为 $2*g^2$ .

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

$(-g,0),...,(-g,g-1),...,(-1,0),...,(-1,g-1)$

$(0,0),...,(0,g-1),...(g-1,0),...,(g-1,g-1)$

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题花了本人整整一天的时间。倘若讲解有不恰当的地方，请多多见谅。菜，求放过!