bzoj#P4253. 密码箱加强版

密码箱加强版

题目描述

由于 BZOJ 的水题已经被 Lcomyn 大爷刷完了,所以机房的蒟蒻们决定再出一道水题给 lcomyn 刷。

正巧蒟蒻们最近做了 AHOI2007 密码箱,觉得这题实在太水了。稍微加强一下下依然还是很水的,所以决定把数据范围开大一点送给 Lcomyn 切。

求方程 x21(modn)x ^ 2 \equiv 1 \pmod n 的解,xx 为小于 nn 的非负整数。

输入格式

一行一个数 nn

输出格式

如果方程无解输出 None,否则就按从小到大的顺序输出所有解,两个数之间用空格隔开,行末无多余空格。

样例输入

5

样例输出

1 4

提示

对于 100%100\% 的数据,1n10181 \le n \le 10^{18}

题目来源

By TA