题解：AT_arc152_d [ARC152D] Halftree
hxhhxh
·
·
题解
题意
给定 n,k，有一个 n 个点的图，点编号为 0\sim n-1.图初始为空，你需要做若干次操作，使得图变为一颗树，或说明无解。
操作：选择两个数 x,y，连边 (x,y)，((x+k)\bmod n,(y+k)\bmod n)。
## 做法
$n$ 个点的数有 $n-1$ 条边，而操作每次都会加两条边，所以当 $n$ 为偶数时无解。下记 $d=\gcd(n,k)$。
当 $n$ 为奇数时，考虑将 $i\to (i+k)\bmod n$ 的边加在图上会发生什么。当 $d=1$ 时，裴蜀定理告诉我们所有点都在同一个环上；当 $d>1$ 时，$+\ k$ 对模 $d$ 的余数不会变，它会形成 $d$ 个环。
把他排得好看一点，比如像下面这样：
这是 $n=35,k=10,d=5$ 的情况。
首先，这样的图一定有奇数个环和奇数条射线（由于 $n$）是奇数。在这样的图上，操作相当于连一条边，将它绕中心顺时针旋转 $\frac{2d\pi}{n}$，然后再连旋转后的边。下面把选的边 $(x,y)$ 标红，$((x+k)\bmod n,(y+k)\bmod n)$ 标蓝。
先把大部分射线上的所有点连起来：
由于射线的个数是奇数，这样一定会剩下一条。考虑如何把这些链连起来：
注意到，这里剩下的那一条射线的第一个点被我们接入树里了。接下来我们还剩偶数个点。像这样构造：
到这里我们就完成了 $n=35,k=5$ 的构造。把它加以推广就可以对于任何 $n,k$ 都构造出来了。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,d;
vector<array<int,2> >p;
signed main(){
cin>>n>>k;
if(n%2==0) return puts("-1"),0;//唯一的无解情况
d=__gcd(n,k);
printf("%lld\n",n/2);
auto add=[&](int x,int y){p.push_back({x,y});};//add(x,y)表示选择 (x,y)
for(int j=0;j<n/d-1;j+=2) add(j*k%n,(j+n-1)*k%n);//第一个环
for(int i=1;i<d;i++){
for(int j=0;j<n/d-1;j+=2) add((j*k+i-1)%n,(j*k+i)%n);//连接第 i-1 个环和第 i 个环
if(i&1) add((i-k-k+n+n)%n,(i-k+n+1)%n);//最后一步的构造
}
for(auto i:p) printf("%lld %lld\n",i[0],i[1]);
}
```