ACM-ICPC Japanese Alumni Group Summer Camp 2015 Day 4. The problem set was also used in Open Cup GP of Japan.

In short,

- Using Chinese Remainder Theorem, and solve the equation in each
*p*^{e}where . - Combine the results.

More precisely,

The problem is, "For given *N*, find the minimum positive integer *k*, such that for all 0 < *a* < *N*, ."

For a prime *p*, . Thus, if *p*^{2} is a divisor of *N* for some *p*, then the answer is "-1" (which means there is no such *k*).

Now, we can assume that *N* can be represent as *p*_{1} * *p*_{2} * ... * *p*_{r}, by some distinct prime numbers *p*_{i}. (That is, *N* is square-free number.)

From the Chinese Remainder Theorem, the answer *k* is the minimum positive integer, such that for all *i* and for all 0 < *a* < *p*_{i}, .

From the well-known theorem called "Fermat's little theorem", such *k* is the minimum positive integer, such that for all *i*, .

Now, we'll fix some *i*, and determine the constraints of *k* by solving the formula "".

Of course, if , then there are no such *k*. (So, the answer is "-1".)

Otherwise, such *k* is the multiplies of *d*_{i}, where *d*_{i} is the "Multiplicative order of ".

That *d*_{i} is a divisor of φ(*p*_{i} - 1), where φ is the "Euler's totient function". (You can also use the "Carmichael's lambda function" instead of Euler's totient function.)

Now, we want to determine minimum positive integer *k*, such that for all *i*, *k* is the multiply of *d*_{i}. This is of course .

Summarizing the above,

- Factorize
*N*into*p*_{1}* ... **p*_{r}, and check whether it is square free. - For each
*p*_{i}, check . - For each
*p*_{i}, calculate the*d*_{i}by brute force on the divisors of φ(*p*_{i}- 1) (or, λ(*p*_{i}- 1)). - Report .

The sample implementation is available in here: http://jag2015summer-day4.contest.atcoder.jp/submissions/495773