题目描述

BB

痛失一血（打了场Comet OJ回来就没了）

不过后来又刷了一道水题

题解

LCM+取模=结论题

结论1

\(gcd(k^{2^i}+1,k^{2^j}+1)=1 (i\neq j 且k为偶数)\)

证明：

设i<j

若存在\(q\mid k^{2^i}+1\)，则\(k^{2^i}\equiv -1(mod \;q)\)

那么\(k^{2^{i+k}}\equiv 1(mod \;q)\)（k>0），则\(k^{2^j} \equiv 1(mod \;q)\)，\(k^{2^j}+1 \equiv 2(mod \;q)\)

update:注意上面的k，此k非彼k

当q>2时无解，当q=2时由于k为偶数，所以k的幂+1为奇数，不存在为2的因子（即无解）

所以gcd=1

结论2

\(gcd(k^{2^i}+1,k^{2^j}+1)=2 (i\neq j 且k为奇数)\)

证明：

同上，可以发现只存在q=2的公因数

乱搞

简单又自然

先特判掉模数为2

①K不是P的倍数

如果K不是P的倍数，那么把式子拆开后变成

\(ans=\sum_{i=0}^{2^{r-l+1}-1}{({k^{2^l}})^i}\)

设\(a={k^{2^l}}\)，则\(ans=\sum_{i=0}^{2^{r-l+1}-1}{a^i}\)

2^l和\(2^r\)可以快速幂求，因为a⁰=a^p-1 mod p=1，可以发现模数实际上是(P-1)

剩下的就是一个等比数列求和

因为K不是P的倍数且P为质数，所以\(k^{2^{i}}\)必定不为0，\(k^{2^{i}}-1\)（等比数列求和的分母）不会为-1

但是\(k^{2^{i}}\)可能为1，这样的话\(ans=2^{r-l+1}\)

②K是P的倍数

显然ans=1

如果K为奇数，那么就还要除掉多出来的的2^R-L

code

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#define fo(a,b,c) for (a=b; a<=c; a++)

#define fd(a,b,c) for (a=b; a>=c; a--)

using namespace std;

long long K,L,R,mod,Mod,S,ans;

int Q,i,j,k,l;

long long qpower(long long a,long long b)

{

	long long ans=1;

	while (b)

	{

		if (b&1)

		ans=ans*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return ans;

}

void js()

{

	long long s1,s2,S1,S2;

	--mod;

	s1=qpower(2,R+1);

	s2=qpower(2,L);

	s1-=s2;

	if (s1<0)

	s1+=mod;

	++mod;

	S1=qpower(K,s1);

	S2=qpower(K,s2);

	if (S2>1)

	ans=(S1*S2%mod-1)*qpower(S2-1,Mod)%mod;

	else

	ans=qpower(2,R-L+1);

	if (ans<0)

	ans+=mod;

}

int main()

{

//	freopen("51nod_1820_4_in.txt","r",stdin);

//	freopen("51nod1820.in","r",stdin);

//	freopen("51nod1820.out","w",stdout);

	scanf("%d",&Q);

	for (;Q;--Q)

	{

		scanf("%lld%lld%lld%lld",&K,&L,&R,&mod);

		Mod=mod-2;

		if (mod==2)

		{

			if (K&1)

			printf("0\n");

			else

			printf("1\n");

			continue;

		}

		if (!(K%mod))

		ans=1;

		else

		{

			ans=0;

			js();

		}

		if (K&1)

		ans=ans*qpower((mod+1)/2,R-L)%mod;

		printf("%lld\n",ans);

	}

}

巴特西

51nod1820 长城之旅

题目描述

BB

题解

结论1

结论2

乱搞

code

最新文章

热门文章