牛客周赛 Round 50题解

前言

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