51nod 1820 长城之旅

发表于 更新于 分类于

长城之旅

或许是全网第一篇能看的题解 (?)

首先\(\text{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}\)
根据定义可以证明。

关于\(\gcd\)的一个结论。
\(\gcd(k^{2^l}+1,k^{2^r}+1)=(k\& 1)?2:1\ ,r>l\)

分类讨论一下 1. \(k\%2=0\)时，假设\(k^{2^l}+1\)有约数\(d\)，即\(k^{2^l}\equiv -1\pmod d\)，又\((k^{2^l})^{2^j}=k^{2^{l+j}},j\ge0\)，所以\(k^{2^r}\equiv 1\pmod d\)，\(k^{2^r}+1\equiv 2\pmod 2\) ，所以\(k^{2^l}+1\)的约数都不是\(k^{2^r}+1\)的约数，当然\(d=2\)需要单独讨论一下，显然\(k^{2^l}+1\)是奇数。 2. \(k\%2=1\)时，唯一区别是\(k^{2^l}+1\)是偶数，\(\gcd=2\)

所以做法就比较显然。
模数是\(2\)的单独处理。

\(k\%p=0\)，显然答案是\(1\)

其余情况，假设\(a=k^{2^l}\)
则乘积等于\((a+1)\times (a^{2^1}+1)\times (a^{2^2}+1)\times ... \times (a^{2^{r-l}}+1)\)
因为每个括号要不选前一个，要不选后一个，所以最后答案是\(\sum_{i=0}^{2^{r-l+1}-1}a^i\)，这东西显然是个等比数列求和。

注意此时只是算出了所有数乘积，最后如果\(k\)时奇数还得除一个\(2^{r-l}\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll k, l, r, p;
int -;

ll fpow(ll a, ll b, ll p) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % p) if (b & 1) res = res * a % p;
	return res; 
}

int main() {
    for (scanf("%d", &-); -; ---) {
    	scanf("%lld %lld %lld %lld", &k, &l, &r, &p);
    	if (p == 2) {
    		printf("%d\n", (k & 1) ? 0 : 1);
    		continue;
    	}
    	ll res = 0;
    	if (k % p == 0)
    		res = 1;
    	else {
    		ll a = fpow(k, fpow(2, l, p - 1), p);
            if (a != 1) {
                res = fpow(a, fpow(2, r - l + 1, p - 1), p);
                res = (res - 1 + p) % p;
                res = res * fpow((a - 1 + p) % p, p - 2, p) % p;
            } else {
                res = fpow(2, r - l + 1, p);
            }
    	}
    	if (k & 1) res = res * fpow(fpow(2, r - l, p), p - 2, p) % p;
        printf("%lld\n", res);
    }
    return 0;
}