题意
定义
$$
F(x,a,b)=\begin{cases}
0&a=0\lor b=0,\\
\gcd(x^a-1,x^b-1)+1&otherwise.
\end{cases}
\quad(x>0,\ a,b\ge0)
$$
给定 $m,a,b,c,d$，求集合 $(F(m,a,b),F(m,c,d)]\cap\mathbb Z$ 的和为 $m$ 的倍数的子集数。
答案对 $998244353$ 取模。
F
$$
\begin{align*}
F(x,a,b)&=\gcd(x^a-1,x^b-1)+1\\
&=\gcd(x^b-1,(x^a-1)-(x^b-1))+1\\
&=\gcd(x^b-1,x^b(x^{a-b}-1))+1\\
&=\gcd(x^b-1,x^{a-b}-1)+1&(x^b-1\perp x^b)\\
&=F(x,b,a-b).
\end{align*}
$$
其中 $0<b<a$.
可以发现这是一个辗转相除的过程，所以 $F(x,a,b)=x^{\gcd(a,b)}\quad(a,b\ne0)$.
65%
列出生成函数
$$
f(x)=\prod_{i=0}^{m-1}x^i+1
$$
令 $k=\frac{R-L}m$，则答案为
$$
\sum_{i\ge0}[x^{im}]f(x)^k
$$
其本质是循环卷积，$O(m^2)$ 计算 $f(x)$ 之后再 $O(m\log m\log k)$ 多项式快速幂即可。
100%
单位根反演
$$
\begin{align*}
\sum_{i\ge0}[x^{im}]f(x)^k&=\sum_{i\ge0}[m|i][x^i]f(x)^k\\
&=\sum_{i\ge0}[x^i]f(x)^k\frac1m\sum_{t=0}^{m-1}w_m^{it}\\
&=\frac1m\sum_{t=0}^{m-1}\sum_{i\ge0}({w_m^t})^i[x^i]f(x)^k\\
&=\frac1m\sum_{t=0}^{m-1}f(w_m^t)^k
\end{align*}
$$
令 $d=\gcd(m,t),s=\frac td,n=\frac md$，则
$$
f(w_m^t)=\prod_{i=0}^{m-1}w_m^{it}+1=(\prod_{i=0}^{n-1}w_n^{is}+1)^d=(\prod_{i=0}^{n-1}w_n^i+1)^d
$$
所以
$$
\begin{align*}
\frac1m\sum_{t=0}^{m-1}f(w_m^t)^k&=\frac1m\sum_{d|m}\sum_{t=0}^{m-1}\\gcd(m,t)=d](\prod_{i=0}^{n-1}w_n^i+1)^{kd}\\
&=\frac1m\sum_{d|m}\varphi(n)(\prod_{i=0}^{n-1}w_n^i+1)^{kd}
\end{align*}
$$
根据代数基本定理
$$
x^n-1=\prod_{i=0}^{n-1}x-w_n^i
$$
代入 $x=-1$
$$
\begin{align*}
(-1)^n-1&=\prod_{i=0}^{n-1}-1-w_n^i\\
1-(-1)^n&=\prod_{i=0}^{n-1}w_n^i+1
\end{align*}
$$
所以
$$
\frac1m\sum_{d|m}\varphi(n)(\prod_{i=0}^{n-1}w_n^i+1)^{kd}=\frac1m\sum_{d|m\land2\nmid n}\varphi(n)2^{kd}
$$
$O(m)$ 预处理 $\varphi(n)$，再 $O(Td(m)\log km)$ 计算即可，其中 $d(m)$ 为 $m$ 的正因子个数。