xy0v0's Blog

Back

题目#

Problem Statement#

You are given positive integers NN and MM. For each k=0,1,…,M−1k = 0, 1, \dots, M-1, solve the following problem.

  • Determine whether there exists a positive integer tt satisfying the following condition, and if it exists, find the minimum such tt.
    • There exists a positive divisor xx of NtN^t such that x≡k(modM)x \equiv k \pmod{M}.

思路#

k=0k=0 的情况不难想到分解素因数,考虑写作 M=∏ipiei,N=∏ip′iei′M=\prod_i p_i ^ {e_i}, N=\prod_i {p'}_i^{e'_i} ,若 ∃pi:∀pi′,pi≠pi′\exists p_i : \forall p'_i,p_i \ne p'_i ,则不可行,否则考虑 max⁡pi=pj′{⌈eiej′⌉}\max_{p_i=p'_j}\{\lceil\frac {e_i} {e'_j}\rceil\} 即可。

沿着这个方向考虑,如果我们得到了 k=1k=1 的情况,那么 pmod  M,p∈pi′p \mod M,p\in p'_i 也是可以容易得到的。显然:kk 可以表示,当且仅当从 1mod  M1 \mod M 开始,通过反复乘上某个 p′p' 并对 MM 取模,可以达到 kk .

因此,穷尽上述操作能够到达的所有余数后,未被到达的余数恰好就是无解的情况。

写成转移:

r⟶rd mod M,d∣N.r\longrightarrow rd\bmod M,d\mid N.

枚举 dd 是困难的,不妨将 NN 写作一个包含重复因子的序列,对序列中每一项,考虑是否加入,如果加入就进行一次如上的转移。这样,一整轮恰好对应乘上一个 NN 的约数。因此可以建立状态 (i,r)(i,r),表示当前处理位置和余数;每条边处理一个因子,位置循环前进。从 (0,1 mod M)(0,1\bmod M) 做普通 BFS,到达 (0,k)(0,k) 的最短距离一定是 LL 的倍数,除以 LL 就得到最小轮数。

代码#