# 2.题解

G

(

x

)

=

{

1

,

2

x

2

,

2

x

g

c

d

(

k

2

i

+

1

,

k

2

i

+

1

+

1

)

=

g

c

d

(

k

2

i

+

1

,

k

2

i

+

1

k

2

i

)

=

g

c

d

(

k

2

i

+

1

,

k

2

i

×

(

k

2

i

1

)

)

=

g

c

d

(

k

2

i

+

1

,

k

2

i

1

)

=

g

c

d

(

(

k

2

i

+

1

)

(

k

2

i

1

)

,

k

2

i

1

)

=

g

c

d

(

2

,

k

2

i

1

)

=

G

(

k

)

begin{aligned}令 G (x) = begin{cases} 1, 2 mid x \ 2, 2 nmid x end{cases}\gcd (k^{2^{i}} + 1, k^{2^{i + 1}} + 1) &= gcd (k^{2^{i}} + 1, k^{2^{i + 1}} - k^{2^{i}})\&= gcd (k^{2^{i}} + 1, k^{2^{i}} times (k^{2^{i}} - 1))\&= gcd (k^{2^{i}} + 1, k^{2^{i}} - 1)\&= gcd ((k^{2^{i}} + 1) - (k^{2^{i}} - 1), k^{2^{i}} - 1)\&= gcd (2, k^{2^{i}} - 1)\&= G (k)end{aligned}

G(x)={1,2x2,2xgcd(k2i+1,k2i+1+1)=gcd(k2i+1,k2i+1k2i)=gcd(k2i+1,k2i×(k2i1))=gcd(k2i+1,k2i1)=gcd((k2i+1)(k2i1),k2i1)=gcd(2,k2i1)=G(k)

l

c

m

i

=

l

r

(

k

2

i

+

1

)

m

o

d

p

=

l

c

m

(

l

c

m

i

=

l

r

2

(

k

2

i

+

1

)

,

(

k

2

r

1

+

1

)

×

(

k

2

r

+

1

)

g

c

d

(

k

2

r

1

+

1

,

k

2

r

+

1

)

)

=

l

c

m

(

l

c

m

i

=

l

r

2

(

k

2

i

+

1

)

,

(

k

2

r

1

+

1

)

×

(

k

2

r

+

1

)

G

(

k

)

)

=

l

c

m

(

l

c

m

i

=

l

r

3

(

k

2

i

+

1

)

,

(

k

2

r

2

+

1

)

×

(

k

2

r

1

+

1

)

×

(

k

2

r

+

1

)

G

(

k

)

×

G

(

k

)

)

=

.

.

.

begin{aligned}mathrm{lcm}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= lcm (lcm_{i = l}^{{r - 2}} (k^{2^{i}} + 1), frac{(k^{2^{r - 1}} + 1) times (k^{2^{r}} + 1)}{gcd (k^{2^{r - 1}} + 1, k^{2^{r}} + 1)} )\&= lcm (lcm_{i = l}^{{r - 2}} (k^{2^{i}} + 1), frac{(k^{2^{r - 1}} + 1) times (k^{2^{r}} + 1)}{G (k)} )\&= lcm (lcm_{i = l}^{{r - 3}} (k^{2^{i}} + 1), frac{(k^{2^{r - 2}} + 1) times (k^{2^{r - 1}} + 1) times (k^{2^{r}} + 1)}{G (k) times G (k)} ) \ &=... end{aligned}

lcmi=lr(k2i+1)modp=lcm(lcmi=lr2(k2i+1),gcd(k2r1+1,k2r+1)(k2r1+1)×(k2r+1))=lcm(lcmi=lr2(k2i+1),G(k)(k2r1+1)×(k2r+1))=lcm(lcmi=lr3(k2i+1),G(k)×G(k)(k2r2+1)×(k2r1+1)×(k2r+1))=...

l

c

m

i

=

l

r

(

k

2

i

+

1

)

m

o

d

p

=

i

=

l

r

(

k

2

i

+

1

)

G

(

K

)

r

l

m

o

d

p

=

i

=

l

r

(

k

2

i

+

1

)

G

r

l

(

K

)

m

o

d

p

begin{aligned}mathrm{lcm}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= frac{prod_{i = l}^{r} (k^{2^{i}} + 1)}{G(K)^{r - l}} bmod p\&= frac{prod_{i = l}^{r} (k^{2^{i}} + 1)}{G^{r - l}(K)} bmod pend{aligned}

lcmi=lr(k2i+1)modp=G(K)rli=lr(k2i+1)modp=Grl(K)i=lr(k2i+1)modp

i

=

l

r

(

(

k

2

l

)

i

l

+

1

)

prod_{i = l}^{r} ((k^{2^{l}})^{i - l} + 1)

i=lr((k2l)il+1) 就是

i

=

0

r

=

2

r

l

+

1

1

(

k

2

l

)

i

sumlimits_{i = 0}^{r = 2^{r - l + 1} - 1} (k^{2^{l}})^i

i=0r=2rl+11(k2l)i (二进制拆分的唯一性)

(

k

2

l

)

2

r

l

+

1

1

k

2

l

1

=

k

2

r

+

1

1

k

2

l

1

begin{aligned} frac{(k^{2^{l}})^{2^{r - l + 1}} - 1}{k^{2^{l}} - 1}\= frac{k^{2^{r + 1}} - 1}{k^{2^{l}} - 1}end{aligned}

k2l1(k2l)2rl+11=k2l1k2r+11

l

c

m

i

=

l

r

(

k

2

i

+

1

)

m

o

d

p

=

k

2

r

+

1

1

(

k

2

l

1

)

×

G

r

l

(

K

)

begin{aligned}mathrm{lcm}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= frac{k^{2^{r + 1}} - 1}{(k^{2^{l}} - 1) times G^{r - l}(K)}end{aligned}

lcmi=lr(k2i+1)modp=(k2l1)×Grl(K)k2r+11

k

m

o

d

p

=

=

0

k bmod p == 0

kmodp==0 时要搞很多奇怪的东西，去 ？ 好了。

k

m

o

d

p

=

=

0

k bmod p == 0

kmodp==0 时，

2

r

+

1

m

o

d

(

p

1

)

2^{r + 1} bmod (p - 1)

2r+1mod(p1) 如果为零，则它会算出来一个

k

0

m

o

d

p

=

1

k ^ 0 bmod p = 1

k0modp=1，所以不对，这时候改为返回值为

0

0

0 就好了。

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define db double
#define LL long long
#define ULL unsigned long long
#define PII pair <int, int>
#define MP(x,y) make_pair (x, y)
#define rep(i,j,k) for (int i = (j); i <= (k); ++i)
#define per(i,j,k) for (int i = (j); i >= (k); --i)

template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
void read (T &x) {
x = 0; T f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar ();
}
x *= f;
}
template <typename T, typename... Args>
void read (T &x, Args&... args) {
}
char For_Print[25];
template <typename T>
void write (T x) {
if (x == 0) { putchar ('0'); return; }
if (x < 0) { putchar ('-'); x = -x; }
int poi = 0;
while (x) {
For_Print[++poi] = x % 10 + '0';
x /= 10;
}
while (poi) putchar (For_Print[poi--]);
}
template <typename T>
void print (T x, char ch) {
write (x); putchar (ch);
}

const LL Mod = 1e9 + 7;

LL sqre (LL x) { return x * x % Mod; }
void del (LL &x, LL y) { ((x -= y) < 0) && (x += Mod); }
void add (LL &x, LL y) { ((x += y) >= Mod) && (x -= Mod); }

LL t, k, l, r, p;

LL quick_pow (LL x, LL y, LL M) {
LL res = 1;
while (y) {
if (y & 1) res = (res * x) % M;
x = (x * x) % M; y >>= 1;
}
return res;
}
LL inv (LL x, LL M) {
return quick_pow (x, M - 2, M);
}
LL G (LL x) {
return (x % 2 == 0 ? 1 : 2);
}
LL f (LL x) {
return k % p == 0 ? 0 : quick_pow (k, quick_pow (2, x, p - 1), p);
}

int main () {
// freopen ("D:\lihan\1.in", "r", stdin);
// freopen ("D:\lihan\1.out", "w", stdout);
while (t--) {
read (k, l, r, p);

if (p == 2) {
printf ("%dn", (k % 2 == 1 ? 0 : 1));
continue;
}

LL res = 0;
if (f (l) == 1) {
res = quick_pow (2, r - l + 1, p);
}
else {

//			printf ("f (r + 1) = %lld, f (l) = %lldn", f (r + 1), f (l));

res = f (r + 1) - 1 + p;
res = (res * inv (f (l) - 1 + p, p)) % p;
}

//		cout << res << endl;

res *= inv (quick_pow (G (k), r - l, p) % p, p);
res = (res % p + p) % p;
print (res, 'n');
}
return 0;
}


# 3.一些编辑很久的错误式子，pi用没有?，下次我就要用这个出题 /wx

g

c

d

i

=

l

r

(

k

2

i

+

1

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

g

c

d

i

=

l

+

1

r

(

(

k

2

i

+

1

)

(

k

2

i

1

+

1

)

)

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

g

c

d

i

=

l

+

1

r

(

k

2

i

k

2

i

1

)

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

g

c

d

i

=

l

+

1

r

(

k

2

i

1

2

k

2

i

1

)

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

g

c

d

i

=

l

+

1

r

(

k

2

i

1

×

k

2

i

1

k

2

i

1

)

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

g

c

d

i

=

l

+

1

r

(

k

2

i

1

×

(

k

2

i

1

1

)

)

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

k

2

l

g

c

d

i

=

l

+

1

r

(

k

2

i

1

1

)

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

g

c

d

i

=

l

r

1

(

k

2

i

1

)

)

m

o

d

p

begin{aligned}mathrm{gcd}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( (k^{2^{i}} + 1) - (k^{2^{i - 1}} + 1) Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i}} - k^{2^{i - 1}} Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1} cdot 2} - k^{2^{i - 1}} Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1}} times k^{2^{i - 1}} - k^{2^{i - 1}} Big) bigg) bmod p \&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1}} times (k^{2^{i - 1}} - 1) Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), k^{2^{l}} cdot mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1}} - 1 Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l}^{r - 1} Big( k^{2^{i}} - 1 Big) bigg) bmod pend{aligned}

gcdi=lr(k2i+1)modp=gcd((k2l+1),gcdi=l+1r((k2i+1)(k2i1+1)))modp=gcd((k2l+1),gcdi=l+1r(k2ik2i1))modp=gcd((k2l+1),gcdi=l+1r(k2i12k2i1))modp=gcd((k2l+1),gcdi=l+1r(k2i1×k2i1k2i1))modp=gcd((k2l+1),gcdi=l+1r(k2i1×(k2i11)))modp=gcd((k2l+1),k2lgcdi=l+1r(k2i11))modp=gcd((k2l+1),gcdi=lr1(k2i1))modp

g

c

d

i

=

l

r

(

k

2

i

1

)

=

g

c

d

(

k

2

l

1

,

g

c

d

i

=

l

+

1

r

(

k

2

i

k

2

i

1

)

)

m

o

d

p

=

g

c

d

(

k

2

l

1

,

k

2

l

g

c

d

i

=

l

r

1

(

k

2

i

1

)

)

m

o

d

p

=

(

k

2

l

1

)

m

o

d

p

begin{aligned}mathrm{gcd}_{i = l}^{r} Big( k^{2^{i}} - 1 Big)&= gcd Big( k^{2^{l}} - 1, mathrm{gcd}_{i = l + 1}^{r} (k^{2^{i}} - k^{2^{i - 1}}) Big) bmod p\&= gcd Big( k^{2^{l}} - 1, k^{2^{l}} cdot mathrm{gcd}_{i = l}^{r - 1} (k^{2^{i}} - 1) Big) bmod p\&= (k^{2^{l}} - 1) bmod pend{aligned}

gcdi=lr(k2i1)=gcd(k2l1,gcdi=l+1r(k2ik2i1))modp=gcd(k2l1,k2lgcdi=lr1(k2i1))modp=(k2l1)modp

g

c

d

i

=

l

r

(

k

2

i

+

1

)

m

o

d

p

=

g

c

d

(

(

k

2

l

+

1

)

,

(

k

2

l

1

)

)

m

o

d

p

begin{aligned}mathrm{gcd}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= gcd ((k^{2^{l}} + 1), (k^{2^{l}} - 1)) bmod pend{aligned}

gcdi=lr(k2i+1)modp=gcd((k2l+1),(k2l1))modp

THE END