寒鸽儿のBlog

结论的话,传到话的人号码是素数,并且这个数字的两倍大于n,答案为1,否则为2.

伪证(以下涉及的序号均为衣服上的数字而非人的序号):
设号码为$t$, $t = k + 1$.若t为素数,则它与$2...2t$-$1$的除了$t$外的数均互质,故而答案为1。
然后,若t为素数但是$2t <= n$,这样,1次传话后未被传达的数为$nt, t\in \{2, 3, 4, ...\}$。由于t为素数,故$t > 1$.所以这些数会在第2天传话中被$t-1$或$t+1$传到。
若$t$不为素数,第一轮传话之后,没有被传到话的人包括:$t$的所有质因数,$t$的质因数的正整数倍。但是,$t-1$与这些数字都是互素的,所以这些数字都会在第2天被传到。

#include <iostream>
#include <cmath>
#define ull unsigned long long

using namespace std;

int main() {
	ull n, k;
	int sqt;
	cin >> n >> k;
	n++; k++;
	sqt = (int)sqrt(k) + 1;		//不能加太大不然对于小的数sqrt_x + 10甚至会大于x
	bool flag = true;
	if(!(k%2) && k != 2) flag = false;
	for(int i = 3; i <= sqt && flag; i += 2)
		if(!(k%i))
			flag = false;
	if(flag) {
		if((k<<1) > n) cout << 1 << endl;
		else cout << 2 << endl;
	} else {
		cout << 2 << endl;	
	}
	return 0;