Part 1. GCD
1.CF185D - Visit of the Great [α]
设 \(d=\gcd(k^{2^a}+1,k^{2^b}+1),(a<b)\)，则：
\[k^{2^a}\equiv k^{2^b}\equiv-1(\bmod d) \]所以
\[1\equiv(-1)^{2^{b-a}}\equiv k^{2^a*2^{b-a}}\equiv k^{2^b}\equiv1(\bmod d) \]所以 \(d\) 为 \(1\) 或 \(2\)。
设 \(t=(k^{2^l}+1)(k^{2^{l+1}}+1)...(k^{2^r}+1)\)，
则当 \(d=2\)，即 \(k\) 为奇数时 \(ans=\dfrac t{2^{r-l}}\)，否则 \(ans=t\)。
设 \(a = k^{2^l}\)，则 \(t=(a+1)(a^2+1)...(a^{2^{r-l}}+1)\)。
考虑到这相当于每次取若干个 \(a\) 和若干个 \(1\) 最后求和，发现每次取的 \(a\) 幂次都是不同的，所以 \(t=\sum_{i=0}^{2^{r-l+1}-1}a^i=\dfrac{a^{2^{r-l+1}}-1}{a-1}=\dfrac{k^{2^{r+1}}-1}{k^{2^l}-1}\)。
但是最后一步等比数列求和要求了 \(a\neq 1\)，所以当算出来 \(a=1\) 时，\(t\) 直接等于 \(2^{r-l+1}\)，很好理解。
另外，当计算 \(a=k^{2^l}\bmod p\) 时，若 \(p|a\) 应直接设 \(a=0\) 而不应使用快速幂，因为费马小定理要求了 \(a\) 不是 \(p\) 的倍数，直接用快速幂计算时若 \(p-1|2^l\) 会出错。还有应为会出现 \(\bmod 1\) 的情况，所以 \(ans\) 初始化为 \(1\bmod p\)。
code
int T;
ll k, l, r, P;
ll qp(ll a, ll b, ll p){
ll ans = 1 % p;
while(b){
if(b & 1){
ans = ans * a % p;
}
a = a * a % p;
b >>= 1;
}
return ans;
}
ll f(ll x){
return k % P == 0 ? 0 : qp(k, qp(2, x, P-1), P);
}
void solve(){
read(T);
while(T--){
read(k, l, r, P);
ll x = (f(l) == 1 ? qp(2, r-l+1, P) : (f(r+1)-1+P) % P * qp((f(l)-1+P)%P, P-2, P) % P);
if(k & 1){
x = x * qp(qp(2, r-l, P), P-2, P) % P;
}
println(x);
}
}