自动搬运

查看原文

来自洛谷，原作者为

	pikabi 逝斯以往，斯人不在，留我一人空悲喜

搬运于2025-08-24 22:12:00，当前版本为作者最后更新于2019-09-16 20:00:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这可真是一道水题，但我比赛时就是没做出来

经过昨天一夜冥思苦想，我想到了一种类数学的证明方法（其实打表找规律更快）————>>

题意

将点权为（i + 1 ) ^ 2 - 1 , i = 1 ~ n,的这n个点连通。其实这是一颗树，共有n - 1个节点，两点之间的距离是点权的最大公约数。

做法

准备

设停止的地方数为i，f(i) =（i + 1 ) ^ 2 - 1 = i * ( i + 2 ) 。条件① ：存在 i * ( i + 2 ），i = 1 ~ n - 1 与 n * (n + 2) 互质。这样就可以保证已有的n - 1个点加上这个点后所得的数最小（加1）。

正文

1、一开始假设 2 ~ 正无穷 这些数都不满足条件 ①（没有比1更小的，故1不在）。

2、当i = n - 1时，f(n - 1) = (n - 1)(n + 1) , f(n) = n * (n + 2), n - 1以及n + 1与 n 都互质， n + 1 与 n + 2 也必定互质，所以当且仅当n - 1 和n + 2互质时， gcd(f(n - 1),f(n)) = 1。所以只有n - 1为3的倍数时（想想为什模）， 两数不互质， 所以不满足条件①的数从2 ~ 正无穷变成了 4， 7， 10， 13， 16 ，19，22 ……正无穷。

3、f(n - 2) = (n - 2) * n， 与f(n)必定不互质。

4、f(n - 3) = (n - 3) * (n - 1), n - 3 与 n 一定互质（因为剩下来的都是是除以3余1的），n - 1 与 n + 2 不可能互质（如2），转5；

5、f(n - 4) = (n - 4 ) * (n - 2 ), 此时该式已超出4的范围，所以f(4)一定不满足条件①。同上可得奇数可以满足条件①。所以范围又缩小到4， 10， 16， 22 …… 正无穷。；

6、反复以上操作，最终假设我们是机器人我们能进行无数次操作，我们惊奇滴发现10以外的数字都会被排除，只有4 和 10 留在里面， 可以计算得到当n = 4 或n = 10时， 结果为5 或 11， 其余的由于都只有n - 1个节点且权值都为1，故其余答案为n - 1。

终于到了上代码的时间了QAQ

#include <cstdio>
#define ll long long

using namespace std;

ll t, n;

int main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		if(n == 4) printf("5\n");
		else if(n == 10) printf("11\n");
		else printf("%lld\n",n - 1);
	}
	return 0;
} 

ps:这只是作为蒟蒻的我的理解，如果有巨佬能够运用强大的数学方法证明当然更好喽