P11869 状态图
题目描述
小威在数电课上学到了状态转换图，比如下面这张：
现在，他遇到了一个同步时序电路分析的问题，其状态转换图有一定的特点：
假设总共有 $n$ 个节点，分别为 $S_0, S_1, ..., S_{n-1}$。
当时钟信号下一个脉冲为"高（1）"时，节点 $S_x$ 转移到节点 $S_{(x*a+c) \bmod n}$；
当时钟信号下一个脉冲为"低（0）"时，节点 $S_x$ 转移到节点 $S_{(x*b+d) \bmod n}$。
而在本题中，时钟信号的脉冲序列为 101010....
现在小威想知道，对于给定的 $n, a, b, c, d$，是否存在一个时钟周期 $T$，使得从任意节点 $S_x$ 任意时刻（即初始脉冲可能为 0，也可能为 1）出发都能在 $T$ 个脉冲之后回到初始状态（状态包括节点和脉冲两个方面，两状态相同当且仅当节点和脉冲都相同），存在则输出最小的时钟周期 $T_{\min}$ ，否则输出 `inf`。
输入格式
无
输出格式
无
说明/提示
样例 #1 解释如下：
对于第一组数据，节点的状态转换序列可以拆分如下（括号中的是脉冲高/低）：
$S_0(1) \to S_3(0) \to S_2(1) \to S_2(0) \to S_1(1) \to S_0(0) \to S_4(1) \to S_1(0)(\to S_0(1))$，8 个时刻一循环；
$S_3(1) \to S_4(0)(\to S_3(1))$，2 个时刻一循环；
取两个循环周期的最小公倍数 8 即是答案。
对于第二组数据，从 $S_0$ 出发，从 0 脉冲对应时刻开始转移，无论如何也无法回到起始状态（除初始时刻外，不存在同时让节点等于 $S_0$，脉冲为 0 的时刻）。