← 返回题目列表

AtCoder · icpc2015summer_day4_d

D. 恒等函数

中文机器翻译题面 查看原题

问题陈述

给你一个整数 $N$,它大于 $1$。

考虑以下功能:

  • $f(a) = a^N \bmod N$
  • $F_1(a) = f(a)$
  • $F_{k+1}(a) = F_k(f(a))~~(k = 1,2,3,\ldots)$

请注意,我们使用 $\mathrm{mod}$ 来表示整数模运算。 对于非负整数 $x$ 和正整数 $y$,$x \bmod y$ 是 $x$ 除以 $y$ 的余数。

输出最小正整数 $k$,使得 $F_k(a) = a$ 对于所有小于 $N$ 的正整数 $a$。 如果不存在这样的$k$,则输出$-1$。


输入

输入由一行组成,其中包含一个整数 $N$ ($2 \le N \le 10^9$),其含义在问题陈述中描述。

输出

输出最小正整数 $k$,使得对于所有小于 $N$ 的正整数 $a$,$F_k(a) = a$;如果不存在这样的 $k$,则输出 $-1$。


示例输入 1

3

样本输入 1 的输出

1

示例输入 2

4

样本输入 2 的输出

-1

示例输入 3

15

样本输入 3 的输出

2