用于计算 $k_1a_1+k_2a_2+\cdots +k_na_n$ 在 $[0,m]$ 范围内能表示的数的算法。
考虑建点 $0,1\cdots a_1-1$。然后对每个点 $i$，连边 $i\to (i+a_j)\bmod a_1(w=a_j)$，再跑最短路。
于是可以 $O(n\times a\log a)$ 计算出最小的可以表示成 $ka_1+r(0\le r\lt a_1)$ 的数，于是每个 $r$ 对答案的贡献为 $\lfloor \frac {m-\text{dis}(r)}{a_1}\rfloor$。
不难发现可以重新排序选最小的 $a$ 作为 $a_1$，另外每个点的相邻点可以在跑最短路算法时动态计算，这些都有利于卡常和节省空间。
板子题。
给定一个四元环，环上每条边有一个边权，且重复经过则计算多次贡献。
人物从二号点出发，最终回到二号点，问权值不小于 $k$ 的路径的最小权值。
任取一条与二号点相邻的边，设权值为 $w$。设 $\text{dis}(i,j)$ 表示从二号点出发到达 $i$ 号点且距离模 $2w$ 等于 $j$ 的最小距离。
那么从二号点出发能得到的路径的权值集合为 $\{\text{dis}(2,r)+2kw|0\le r\lt 2w,k\ge 0\}$，枚举 $r$ 即可计算答案。
关于为什么选取 $2w$，可以解释为回到 $2$ 号点后可以在任意一条边上来回移动，正确性不难证明。
$T$ 组询问，每组询问给定 $n,k$，求 $n$ 是否能用若干个 $k$ 的不为 $1$ 的因子表示。
数据保证 $k$ 的取值不超过 $50$ 个。
如果 $n$ 能用若干个 $k$ 的不为 $1$ 的因子表示等价于 $n$ 能用 $k$ 的素因子表示。
预处理 $O(\sqrt k)$ 范围的数后对每个 $k$ 进行因式分解，时间复杂度 $O\left(\frac {\sqrt k}{\ln k}\right)$。
如果 $k=1$，显然无解。如果 $k$ 是质数，只需要判定 $k\mid n$ 是否成立。
如果 $k$ 有两种素因子，记为 $a,b$，于是等价于求解 $ax+by=n$ 的非负整数解。
找到最小的 $y$ 满足 $y\equiv nb^{-1}\bmod x$，然后验证此时 $by$ 是否不超过 $n$ 即可。
如果 $k$ 有至少三种素因子，显然 $k$ 的最小素因子不超过 $O\left(k^{\frac 13}\right)$，跑同余最短路算法即可，时间复杂度 $O\left(k^{\frac 13}\log k\right)$。
总时间复杂度 $\left(50\left(\frac{\sqrt k}{\ln k}+k^{\frac 13}\log k\right)\right)$。