#P4253. 密码箱加强版

    ID: 3471 传统题 2000ms 5MiB 尝试: 57 已通过: 10 难度: 7 上传者: 标签>难度分类提高+/省选-数论Miller–RabinPollard–Rho中国剩余定理模逆元欧拉定理快速幂快速乘防溢出枚举与搜索深度优先搜索2-adic 赋值CF2300ByTA

密码箱加强版

密码箱加强版

题目背景

Lcomyn 已经做完了 BZOJ 上的简单题。机房的同学们拿 AHOI 2007 的「密码箱」作原型,扩大了数据范围,请他来做这一加强版。

题目描述

给定正整数 nn,求所有满足

x2≡1(modn),0≤x<nx^2\equiv1\pmod{n},\qquad 0\le x<n

的整数 xx。

输入格式

输入一行一个正整数 nn。

输出格式

当 n=1n=1 时,本题约定输出 None。

其他情况下,将所有解按从小到大的顺序输出在一行,相邻两个数之间用一个空格分隔,行末没有多余空格。若无解,输出 None。

样例 #1

样例输入 #1

5

样例输出 #1

1 4

数据规模与约定

1≤n≤10181\le n\le10^{18}。