「Codeforces 17D」Notepad - 数论

发表于 分类于 ， 阅读次数： Disqus：

题意描述

Codeforces 链接

你有一个本子，你要往上面写全部的长度为 \(n\) 的 \(b\) 进制数字，每一页可以写 \(c\) 个。要求所有数字必须严格不含前导 \(0\)。求最后一页上有多少个数字

数据范围：\(2 \leq b < 10^{10^6}, 1 \leq n < 10^{10^6}, 1 \leq c \leq 10^9\)

题意描述

翻译一下题意，本题即为求出下列式子的值：

\[ (b - 1)b^{n - 1} \bmod c \]

\(b\) 可以对 \(c\) 取模处理掉。而按照本题的数据范围直接进行快速幂显然是不可行的。于是我们可以对式子进行一些变换。

由拓展欧拉定理，我们可以得到下列同余方程：

\[ (b - 1)b^{n - 1} \equiv \begin{cases} (b - 1)(b)^{n - 1} \pmod c & n - 1 < \varphi(c) \\ (b - 1)(b)^{(n - 1) \bmod \varphi(c) + \varphi(c)} \pmod c & n - 1 \geq \varphi(c) \end{cases} \]

当 \(n\) 过大时，我们可直接将其对 \(\varphi(c)\) 取模再进行快速幂计算即可。

这道题我们可以先读入 \(c\)，然后再读入 \(b\)，边读边取模。如果 \(n\) 在 \(9\) 位及以内可以直接读并进行快速幂，否则就先算出 \(\varphi(c)\)，然后边读 \(c\) 边取模。最后计算出结果即可。

代码演示

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
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>

long long read(const std::string &s, long long p) {
    long long ans = 0;
    int len = s.length();
    for (int i = 0; i < len; i++) {
        ans = ans * 10 + s[i] - '0';
        ans %= p;
    }
    return ans;
}

long long phi(long long a) {
    long long ans = a;
    for (long long i = 2; i * i <= a; i++) {
        if (a % i == 0) {
            ans = ans / i * (i - 1);
            while (a % i == 0) a /= i;
        }
    }
    if (a > 1) ans = ans / a * (a - 1);
    return ans;
}

long long pow(long long a, long long k, long long p) {
    long long ans = 1;
    for (; k; k >>= 1, a = a * a % p) if (k & 1) ans = ans * a % p;
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::string bIn, nIn;
    long long c;
    std::cin >> bIn >> nIn >> c;

    long long b = read(bIn, c), n = read(nIn, 1e9), p = phi(c);
    long long k;
    if (n > p || nIn.length() > 9) k = (read(nIn, p) - 1 + p) % p + p;
    else k = n - 1;
    long long ans = (b - 1 + c) % c * pow(b, k, c) % c;

    std::cout << (ans ? ans : c) << '\n';

    return 0;
}