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

Problem D: Identity Function

In short,

1. Using Chinese Remainder Theorem, and solve the equation in each p^e where

   Unable to parse markup [type=CF_TEX]

   .
2. Combine the results.

More precisely,

The problem is, "For given N, find the minimum positive integer k, such that for all

Unable to parse markup [type=CF_TEX]

,

Unable to parse markup [type=CF_TEX]

."

For a prime p,

Unable to parse markup [type=CF_TEX]

. Thus, if p² 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

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

,

Unable to parse markup [type=CF_TEX]

.

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

Unable to parse markup [type=CF_TEX]

.

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

Unable to parse markup [type=CF_TEX]

".

Of course, if

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

".

That d_i is a divisor of

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

.

Summarizing the above,

1. Factorize N into

   Unable to parse markup [type=CF_TEX]

   , and check whether it is square free.
2. For each p_i, check

   Unable to parse markup [type=CF_TEX]

   .
3. For each p_i, calculate the d_i by brute force on the divisors of

   Unable to parse markup [type=CF_TEX]

   (or,

   Unable to parse markup [type=CF_TEX]

   ).
4. Report

   Unable to parse markup [type=CF_TEX]

   .

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