link。

简单提一下做法，注意到 $k^{2^a}\equiv k^{2^b}\equiv-1\equiv (-1)^{2^{b-a}}=1\pmod{(k^{2^a}+1,k^{2^{b}}+1)}$，所以 $\gcd$ 只会是 $1$ 或 $2^{r-l}$，取决于 $k$ 的就行，于是求一个 product 即可。

接下来是这篇题解的重点，聚焦 $\displaystyle \prod\left(k^{2^i}+1\right)=\sum_{i=0}^{2^{r-l+1}-1}\left(k^{2^l}\right)^i$ 做补充。

不妨从二项式乘法的角度来看，举例 $\left(k^{2^i}+1\right)\left(k^{2^j}+1\right)\left(k^{2^w}+1\right)$，不妨将 $k^{2^x}$ 看作是选择，将 $1$ 看作是不选择，那么一个长度为 $r-l+1$ 的二进制数即可表示出这个乘积所有的状态，不妨设这个状态为 $S$，注意到 $S$ 对答案的贡献是在做加法，并且因为类似 $2^i+2^j+2^w$ 的指数相加正好可以凑出 $S$，所以 $S$ 的贡献就是 $\left(k^{2^l}\right)^S$，得证。

void executer() {
    int k, p;
    LL l, r;
    cin >> k >> l >> r >> p;
    SetMod(p-1);
    int e = qpow(2, l), e2 = qpow(2, r-l+1);
    SetMod(p);
    int K = k%p ? qpow(k, e) : 0, ans;
    if (K == 0) {
        ans = 1;
    }
    else {
        if (K == 1) {
            ans = qpow(2, r-l+1);
        }
        else {
            ans = mul(sub(qpow(K, e2), 1), inv(sub(K, 1)));
        }
    }
    if (k%2) {
        mul_eq(ans, inv(qpow(2, r-l)));
    }
    cout << ans << "\n";
}