前言
鉴于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),那么
- u+v为奇数,简化形式为:.
- 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题花了本人整整一天的时间。倘若讲解有不恰当的地方,请多多见谅。菜,求放过!