题意
(T) 组询问，每次给定 (k,l,r,p)，求 ( ext{lcm}(k^{2^l}+1,k^{2^{l+1}}+1,cdots,k^{2^r}+1)mod p)。
(1leqslant Tleqslant 10^5,1leqslant kleqslant 10^6,0leqslant lleqslant rleqslant 10^{18},2leqslant pleqslant 10^9)，保证 (p) 是质数。
分析
小清新数论题。
我们简单猜个结论，任意两个数的 (gcd) 都不会很大。取任意两个位置 (a,b(a<b))，设 (gcd(k^{2^a}+1,k^{2^b}+1)=d)：
[k^{2^a}equiv k^{2^b}equiv -1pmod d\1equiv(-1)^{2^{b-a}}equiv (k^{2^{a}})^{2^{b-a}}equiv k^{2^b}equiv -1pmod d
]
于是 (d=1) 或 (2)，且 (d=2) 当且仅当 (k) 为奇数。
设 (t=prod_{i=l}^r(k^{2^t}+1))，那么答案就是：
[egin{cases}frac{t}{2^{r-l}}&kequiv1pmod 2\t&kequiv 0pmod 2end{cases}
]
那么我们转求 (t) 的值，考虑直接推式子：
[(k^{2^l}+1)((k^{2^l})^2+1)((k^{2^l})^4+1)cdots((k^{2^l})^{2^{r-l}}+1)\=sum_{p=0}^{2^{r-l+1}-1}(k^{2^l})^p=frac{(k^{2^l})^{2^{r-l+1}}-1}{k^{2^l}-1}=frac{k^{2^{r+1}}-1}{k^{2^l}-1}
]
然后直接算就好了，注意特判 (k^{2^l}equiv 1pmod p) 的情况，此时上式的值为：
[(1+1)(1^2+1)(1^4+1)cdots(1^{2^{r-l}}+1)=2^{r-l+1}
]
代码
#include<stdio.h>
int T,k,p;
long long l,r;
int ksm(int a,long long b,int mod){
int res=1;
while(b){
if(b&1)
res=1ll*res*a%mod;
a=1ll*a*a%mod,b>>=1;
}``
return res;
}
int f(long long x){
return k%p==0? 0:ksm(k,ksm(2,x,p-1),p);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%lld%lld%d",&k,&l,&r,&p);
if(p==2)
printf("%d
",(k&1)^1);
else{
int ans=(f(l)==1? ksm(2,r-l+1,p):(1ll*(f(r+1)-1+p)%p*ksm((f(l)-1+p)%p,p-2,p)%p));
if(k&1)
ans=1ll*ans*ksm(ksm(2,r-l,p),p-2,p)%p;
printf("%d
",ans);
}
}
return 0;
}