sxczf's Blog

题面 戳我 题解 戳我

题目大意

10⁵组询问

每次给你k,l,r,p

求LCM(k2l + 1, k2l + 1 + 1, ..., k2r + 1)%p

(1 ≤ ki ≤ 106; 0 ≤ li ≤ ri ≤ 1018; 2 ≤ pi ≤ 109)cf的字体好好看啊

第一眼看上去神题啊QAQ

想了下估计一堆数的lcm肯定是有性质的

猜了下大概gcd是1或者2

然而数学太差不会证

vp结束后看了下题解算是搞懂了

Let . Squaring both sides we get , but we want to . This means, that d can be only 2.

让，左右平方得到，但是我们想让所以d只能是2

然后问题就变成了计算那一堆数字的乘积

不难发现这是只等比数列

套下公式计算下就好了

细节有点复杂导致vp2h内没写出有些悲伤

#include <stdio.h>
#include <algorithm>
using namespace std;
int t;
long long k,l,r,p,a,b,h;
long long ksm(long long x,long long y,long long mo){
	long long k=1;
	for(;y;y>>=1){
		if(y&1)k=1ll*k*x%mo;
		x=1ll*x*x%mo; 
	}
	return k;
}
int main(){
	scanf("%d",&t);
	for(;t;t--){
		scanf("%I64d%I64d%I64d%I64d",&k,&l,&r,&p);
		if(p==2){if(k&1)printf("0\n");else printf("1\n");continue;}
		if(k==1){printf("%I64d\n",2%p);continue;}
		h=1;
		if(k&1)h=ksm(ksm(2,p-2,p),r-l,p);
		if(k%p==0){
			printf("%I64d\n",h);continue;
		}
		else {
			a=ksm(k,ksm(2,r+1,p-1),p)-1;
			b=ksm(k,ksm(2,l,p-1),p)-1;
			if(!b)printf("%I64d\n",ksm(2,r-l+1,p)*h%p);
			else printf("%I64d\n",h*a%p*ksm(b,p-2,p)%p);
		}
	}
	
	return 0;
}