题解 CF185D【Visit of the Great】
whiteqwq
2021-09-07 12:52:54
[CF185D Visit of the Great](https://www.luogu.com.cn/problem/CF185D)解题报告：
[更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/15237270.html)
## 题意
$T$ 组询问，每次给定 $k,l,r,p$，求 $\text{lcm}(k^{2^l}+1,k^{2^{l+1}}+1,\cdots,k^{2^r}+1)\bmod p$。
$1\leqslant T\leqslant 10^5,1\leqslant k\leqslant 10^6,0\leqslant l\leqslant r\leqslant 10^{18},2\leqslant p\leqslant 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 -1\pmod d\\1\equiv(-1)^{2^{b-a}}\equiv (k^{2^{a}})^{2^{b-a}}\equiv k^{2^b}\equiv -1\pmod d$$
于是 $d=1$ 或 $2$，且 $d=2$ 当且仅当 $k$ 为奇数。
设 $t=\prod_{i=l}^r(k^{2^t}+1)$，那么答案就是：
$$\begin{cases}\frac{t}{2^{r-l}}&k\equiv1\pmod 2\\t&k\equiv 0\pmod 2\end{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 1\pmod 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\n",(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\n",ans);
}
}
return 0;
}
```