自动搬运

查看原文

来自洛谷，原作者为

	JuRuo_QAQ 阿巴阿巴阿巴

搬运于2025-08-24 21:58:41，当前版本为作者最后更新于2022-01-10 22:20:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意转化：给出一个数 $n$ ，求 $x^{2} \equiv 1 \pmod n$ 解的个数

原式可化为：$x^{2}-1=k \times n$ 其中 $k$ 是正整数

因式分解可得：$(x+1)(x-1)=k \times n$

即 $n|(x+1)(x-1)$

接下来就很好理解了：需要构造 $a,b$ 使 $a \times b = n$

在 $a^{2}\le n$ 范围内枚举 $a$ 并使

$a|(x-1),b|(x+1)$ 或 $a|(x+1),b|(x-1)$

注：$n=1$ 是唯一无解情况

上代码

#include<cstdio>
#include<set>/*用 set 是为了防止重复答案，如果用数组然后 unique 去重也可以*/
typedef long long ll;//不开 long long 见祖宗
std::set<ll> s;
int main(){
	ll n;
	scanf("%lld",&n);
	if(n==1){puts("None");return 0;}//无解
	puts("1");
	for(register ll i=1;i*i<=n;i++)//枚举 a
		if(n%i==0){//如果满足条件（可以整除）
			ll a=i,b=n/a;
			for(register ll j=b+1;j<=n;j+=b)if((j+1)%i==0)s.insert(j);
			for(register ll j=b-1;j<=n;j+=b)if((j-1)%i==0)s.insert(j);
		}
	for(std::set<ll>::iterator it=s.begin();it!=s.end();it++)printf("%lld\n",*it);//用指针输出比较方便
	return 0;
}