BZOJ1406 密码箱

x2 ≡ 1 (mod n) => x2 = k * n + 1 => n | (x + 1) * (x - 1)

设n = a * b，则 (a | x + 1 且 b | x - 1) 或 (a| x - 1 且 b | x + 1)

于是暴力 $a\in [1,\sqrt n]$

#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
set<ll>::iterator it;
set<ll> S;
ll n;
int main() {
    ll a,b,x;
    scanf("%lld\n",&n);
    for (int i=1;i*i<=n;++i)
        if(n%i==0){
        a=i,b=n/i;
        for (int k=0;(x=b*k+1)<n;++k)
            if ((x+ 1) % a == 0)
                S.insert(x);
        for (int k=1;(x=b*k-1)<n;++k)
            if ((x-1)%a==0)
                S.insert(x);
        }
    for(it=S.begin();it!=S.end();it++)
        printf("%lld\n", *it );
    return 0;
}