A
显然只需要考虑质因子。
首先 \(k\) 只有一个质因子可以特判，有两个可以 exgcd
有三个及其以上那么最小的一个 \(\le 10^5\)，同余最短路即可。
B
考虑一个序列 $\lbrace x|x=a_ib_i^t,t\in \mathbb{N}\rbrace $，对于一个质因子提出了怎样的限制？
设 \(a_i,b_i\) 在质因数 \(p\) 的指数分别是 \(c_{i,p},d_{i,p}\)
则 Ans 设为 \(\prod p_i^{r_i}\)
必然有对于每个 \(p\)，有：
-
\(\forall i,c_{i,p}\le r_p\)
-
\(\forall i,r_p\equiv c_{i,p}(\bmod d_{i,p})\)
-
\(\exists k,\forall p,r_p=c_{i,p}+k·d_{i,p}\)
也就是要求 \(b\) 的指数相同
等价于：
\(\forall p_1,p_2,i,d_{i,p}>0,\frac{r_{p_1}-c_{i,p_1}}{d_{i,p_1}}=\frac{r_{p_2}-c_{i,p_2}}{d_{i,p_2}}\)
限制条件 \(2\) 应当是可解的，会得到一个 \(r_p\equiv h_p(\bmod m_p)\)，限制条件 \(1\) 可以通过调整下界来满足
但是限制条件 \(3\) 就有一点那个
其实可以通过 \(h_p,m_p\) 来反过来对 \(a_ib_i^{k_i}\) 中的 \(k_i\) 提出限制。
类如 \(k_i\equiv x_i(\bmod t_i)\) 这种东西，其实也就是最初的 \(h_p\) 给出的限制，还有后面的 \(m_p\) 给出的限制，这是一个 \(p\) 给一个序列的限制，一个序列的 \(k\) 可以由这些线性同余方程组解出来
解出来之后呢，由于每个 \(k_i\) 是独立的，但是我们要求最终的解答是一样的，所以每个 \(k_i\) 可以通过质因子建立一些关系，这显然也是丢番图方程
嗯貌似可以高斯消元
然后取一组最小的解出来就好了
太TMD扯淡了这个题写起来
\(n\le 100?\)
C
硬算指定死，不过因为 \(C\le 10^6\)，所以可以处理出两个区间每个数字的出现次数，这可以暴力找循环节。注意循环节前面还有一段未进入循环节的部分
而且有 \(\frac{p}{q}+\frac{q}{p}\) 由于呈现倒数关系所以值最大是 \(C+1\)。
考虑设 \(f(x,y)=\frac{x}{y}+\frac{y}{x}\)，考虑求解 \(\sum[\lceil f(x_i,y_i)\rceil \ge k]\)
考虑到这玩意是对勾函数，那么对于一个 \(x_i\) 而言是可以利用二次函数解出一段区间的
现在还是 \(O(C^2)\)，考虑优化
注意到对勾函数存在分界点，也就是 \(x=y\) 的时候，不妨钦定 \(x<y\)，枚举 \(x\)，则这个对勾函数随着 \(y\) 增加而增加，最多取到 \(\frac{C}{y}\)，所以是调和级数复杂度。
D
首先 \(\gcd a_i\) 的肯定是解，然后根据欧拉定理显然不存在大于 \(n\) 的质数符合条件了
那么考虑枚举 \(\le n\) 的质数，利用欧拉定理将其变为 \(p-1\) 阶多项式后判断系数模 \(p\) 是否是全零，同时需要有 \(p|a_0\)。
这东西疑似充要
E
显然可以等效为 \(aFib_n+bFib_{n+1}\equiv 0(\bmod m)\)
自然地除掉 \(\gcd(a,b,m)\) 同时 \(b\) 进行移项，变为 \(a',b',m'\)，则有：
\[a'Fib_n\equiv b'Fib_{n+1}(\bmod m'),\gcd(a',b',m')=1 \]也就相当于 \(a'Fib_n=b'Fib_{n+1}+km'\)。
同时除掉 \(\gcd(a',m')\) 显然也成立，这就要求 \(\gcd(a',m')|b’Fib_{n+1},\gcd(a',b',m')=1\implies \gcd(a',m')|Fib_{n+1}\)。
类似地，也可以得出 \(\gcd(b',m')|Fib_n\)，又因为有 \(\gcd(Fib_n,Fib_{n+1})=1\)，所以类似有 \(\gcd(Fib_n,m')|b',\gcd(Fib_{n+1},m')|a'\)
则有：\(\gcd(Fib_{n+1},m')|a',\gcd(a',m')|Fib_{n+1}\implies \gcd(Fib_{n+1},m')=\gcd(a',Fib_{n+1},m')\)
类似地可以有 \(\gcd(Fib_{n+1},m')=\gcd(a',m')\)
也有 \(\gcd(Fib_n,m')=\gcd(b',m')\)
不妨设 \(x=\gcd(Fib_n,m'),y=\gcd(Fib_{n+1},m')\)
则显然有 \(\gcd(x,y)=1\)，且 \((xy)|m',y|(a'Fib_n),x|(b'Fib_{n+1})\)
所以给原同余式整体除掉 \(xy\) 是可以的，且除掉之后所有数字就互质了
互质就可以求逆元了，同时也说明了 \((\frac{a'}{y},\frac{b'}{x},\frac{m'}{xy})\) 与 \((\frac{Fib_{n+1}}{x},\frac{Fib_n}{y},\frac{m'}{xy})\) 是对应的，因为可以互推。
注意到后面的三元组个数与 \(m\) 的约数和同阶（显然 \(Fib\) 数列循环节长度与模数同阶，手玩易证）
可以暴力处理出来直接哈希表/map 回答询问即可。
F
显然你三个方向两个向外一个向内，所以向外的状态向向内的状态连边，则可以变成一颗二叉树，而原题等价于问两个点之间的距离，显然我们只需要求出 dep 和 lca 即可。
可以考虑倍增，显然我们可以在类似辗转相除法地计算 \(k\) 级祖先，这就好了
标签：Fib,le,frac,gcd,数论,可以,60,day,equiv From： https://www.cnblogs.com/spdarkle/p/18500263