P4296 [AHOI2007] 密码箱题解

· · 题解

题意转化：给出一个数 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;
}