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 pe where
Unable to parse markup [type=CF_TEX]
. - 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 p2 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 pi. (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 di, where di is the "Multiplicative order of
Unable to parse markup [type=CF_TEX]
".That di 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 di. This is of course
Unable to parse markup [type=CF_TEX]
.Summarizing the above,
- Factorize N into
Unable to parse markup [type=CF_TEX]
, and check whether it is square free. - For each pi, check
Unable to parse markup [type=CF_TEX]
. - For each pi, calculate the di by brute force on the divisors of
Unable to parse markup [type=CF_TEX]
(or,Unable to parse markup [type=CF_TEX]
). - Report
Unable to parse markup [type=CF_TEX]
.
The sample implementation is available in here: http://jag2015summer-day4.contest.atcoder.jp/submissions/495773