洛谷4196 AHOI2007 密码箱

可以二次剩余做，然而我不会

$$ x^2=1\left( mod\,\,n \right) \\ x^2-1=kn \\ \left( x+1 \right) \left( x-1 \right) =kn \\ \text{令}x+1=k_1n_1,x-1=k_2n_2 \\ \text{枚举一个大于等于}\sqrt{n}\text{的}n\text{的约数}n_1\text{，然后枚举他的倍数}k_1,\text{计算出}k_1n_1+\text{1和}k_1n_1-\text{1,然后检验即可。} \\ \text{复杂度不会证} $$

#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

std::vector<int_t> divisors;
// std::unordered_set<int_t> divisors_set;
std::set<int_t> result;

int_t n;
int main() {
    cin >> n;
    for (int_t i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(n / i);
        }
    }
    for (int_t d : divisors) {
        for (int_t i = 1; i * d <= n; i++) {
            {
                int_t x = i * d - 1;
                int_t d2 = n / d;
                if ((x - 1) % d2 == 0) {
                    result.insert(x % n);
                }
            }
            {
                int_t x = i * d + 1;
                int_t d2 = n / d;
                if ((x + 1) % d2 == 0) {
                    result.insert(x % n);
                }
            }
        }
    }
    // result.insert(1);
    for (int_t x : result) cout << x << endl;
    return 0;
}