洛谷P5285 [十二省联考2019]骗分过样例

y d c 的题面 * 2

题解

测试点 1 ~ 3 : `1_998244353`

输入：

1_998244353

100000
0
1
2
3
4
5
6
7
8
9
10
....

输出：

1 (=19^0)
19 (=19^1)
361 (=19^2)
6859 (=19^3)
130321
2476099
47045881
893871739
13409040
254771760
...

显然是要求 $19^x$。
但是输出很明显被取模了。你可以直接通过看功能编号看出模数是 $998244353$。或者可以用以下的数学推导过程：

由于在输入中，$19^7 = 893871739$ 没爆模数，但是$19^8 = 893871739 \times 19$ 爆了。所以模数肯定是 $19^8 - 13409040 = 16970154001 = 17 \times 998244353$ 的约数且大于 $893871739$，所以模数只可能是 $998244353$

对于测试点 1，$x < 10^5$，所以可以循环求解，时间复杂度 $O(x_{max})$

对于测试点 2，$x$ 在 long long 范围内，考虑快速幂处理，时间复杂度 $O(n \ log \ x)$

对于测试点 3，$x$ 超出了 long long 范围。根据扩展欧拉定理，$a^b \equiv a^{b\text{ mod }\varphi(m) + \varphi(m)} \pmod m$，由于 $998244353$ 是质数，所以 $\varphi(998244353) = 998244352$，所以在输入时将数字对 $998244352$ 取模，然后快速幂求 $a^{b + 998244352}$ 即可。

预计得分：12

代码见下文。

测试点 4：`1?`

输入：

1?

30000
0
1
2
627811703016764290815178977207148434322
856773959631992699884816425292659199878
....

输出：

这一次没有模数了，需要我们自己思考。

我们发现输出数字并不大，所以模数肯定也不大，所以我们考虑找到输出中最大的数字，然后从那个数字开始枚举，直至找到答案。

输出中最大的数是 $1145099$，在输出数据的第 3303 行和第 23865 行。

所以我们从 $1145099$ 开始枚举，最终枚举到答案是 $1145141$。

照样扩展欧拉定理一波。

预计得分：19

测试点 5：`1?+`

输入：

输出：

...
4780942455857497844
3723979667086536331
4605453201349670131
...

我们发现这一次输出的数字过大，明显无法直接枚举。

所以我们可以考虑测试点 3 的数学计算法。

我们幸运地发现有两组数据十分接近：

1
2
3

7146| 264708066
...
9371| 264708068

再找到它们对应的输出：

1
2
3

7143| 1996649514996338529
...
9368| 1589589654696467295

所以模数一定是 $1996649514996338529 \times 19^2 - 1589589654696467295 = 719200885258981741674$ 的约数。

最后分解下来为 $5211600617818708273$，快速幂处理。注意使用快速乘或者 __int128 来防止爆 long long。

预计得分：28

测试点 6 ~ 7：`1wa_998244353`

输入：

1wa_998244353

100000
0
1
2
3
4
5
6
7
8
...

输出：

出现负数，计算过程中肯定爆 long long 了。

我们注意到题目中的一段话：

如果你的程序希望利用 int 的自然溢出的特性，请转换为 unsigned 类型运算。例如将 a + b 改写为 (int) ((unsigned) a + (unsigned) b)，以避免出现不预期的错误。

所以我们可以运用这个方法。在测试点 6 中，$x \le 10^5$，所以考虑用上面自然溢出的办法模拟求值。

对于测试点 7，数字过大，无法直接模拟，所以考虑求循环节，使用 map 找出循环节，直接求解即可。

预计得分：41

测试点 8 ~ 10：`2p`

我们先随便观察两组输入输出：

1 2	输入：2 10 输出：pp.p.p... 输入：5 10 输出：p.p...

首先非常明显的发现，输出是一个区间。其次，我们发现，如果该字符下标是质数，则该字符是 p，否则是 .

所以这是区间求质数题…

对于测试点 8，$L, R \le 10^6$，直接线性筛。

对于测试点 9 和 10，可以对每个数跑一遍 Miller-Rabin 算法。

预计得分：59

测试点 11 ~ 13：`2u`

首先观察输出，发现只有 +-0 三种符号。
再看编号 2u，基本上就能猜出来这是莫比乌斯函数。

对于测试点 11， $L, R <= 10^6$ ，依旧线性筛解决。

对于剩下的两个测试点，可以打表解决，也可以使用如下的非打表算法：

首先，先筛出 $2$ ~ $10^6$ 之间的质数。然后，对于给定区间里的数，我们先用这些小于 $10^6$ 的质数去进行分解。过程中注意一旦筛到 $n$ 有平方数因子就把 $\mu (n)$ 直接设为 $0$，且计算筛到质数的乘积。

此时，如果用完小于 $10^6$ 的质数进行分解后，筛到的乘积仍然小于原数，只有以下三种情况：

剩下这个数是质数。

判断方法： Miller-Rabin 一遍即可。（强调一遍，只要用一个 $2$ 判断就可以了！）
2. 剩下这个数是平方数。判断方法： 将剩下这个数 sqrt 后判断即可。（有些大佬没判这个也 A 了，为了保险我还是判了）
3. 剩下这个数是两个不同的，大于 $10^6$ 的质数之积。
只要上述两个条件均不成立，那这个条件自然成立。

可以证明，剩下的数肯定不会是三个及以上大于 $10^6$ 的质数的乘积。

预计得分：79

测试点 14~15：`2g`，测试点 16：`2g?`

看出这三个点需要较强的数论知识，因为如果不知道原根是很难看出来的。

不过只要写过求原根，或者 N 次剩余和 NTT 代码的都应该知道原根。

如果您不会相关知识，您可以看下面的概念：

阶：对于两个互质的数 $a,n$，定义 $a$ 模 $n$ 的阶为满足 $a^d \equiv 1 \pmod n$ 的最小正整数 $d$。记作 $\delta _n(a)$。由欧拉定理可知，$\delta _n(a) | \varphi(n)$。

原根：如果 $\delta _n(a) = \varphi(n)$，则 $a$ 是模 $n$ 意义下的原根。一般用 $g$ 表示。

指标：记作 $\operatorname{ind}_g x$，表示一个数 $x$ 在 $\mod p$ 意义下关于原根 $g$ 的离散对数。

那么，如何求原根呢？

很简单，根据原根的定义，对于模数 $p$ 和一个数 $a$，如果对于任意一个 $\varphi(p)$ 的质因子 $q$，有 $a^{\frac{\varphi(p)}{q}} \equiv 1 \pmod p$。那么 $a$ 就不是 $p$ 的原根。

对于测试点 14，对模数质因子分解，暴力判断即可。

测试点 15 模数发生了变化，直接暴力跑不过去。考虑用指标做。

先找出模数的一个原根 $6$，然后线性扫一遍指标。当一个数的指标与 $\varphi(p)$ 互质时，该数就是 $p$ 的原根，否则不是。

测试点 16 需要自己找模数，这个别的大佬都讲过了，模数是 $1515343657$，用测试点 14 的方法暴力即可。

代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define _rep(i, x, y) for (int i = x; i <= y; i++)
#define LL long long
using namespace std;
LL mo = 998244352;
template <typename T>
inline void read(T &x) {
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void readmo(T &x) { // 读入时对 mo 取模。
    x = 0;
    LL f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
        x %= mo;
    }
    x *= f;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
string utensil; // 读入的类别。
LL qmul(LL a, LL b, LL p) { // 使用 __int128 快速乘。
    return (__int128) a * b % p;
}
LL qpow(LL a, LL b, LL p) { // long long 意义下的快速幂，使用了快速乘。
    LL sum = 1;
    while (b) {
        if (b & 1)
            sum = (__int128)sum * a % p;
        a = ((__int128)a * a) % p;
        b >>= 1;
    }
    return sum;
}

vector<int> prefix, answer; 
int b, p;
void pretreatment() { // 寻找循环节。
    int mod = 998244353;
    int c = 1;
    map<int, int> m; // 存放数字，以寻找循环节。
    m[1] = 0;
    prefix.push_back(1);
    for (int i = 1;; i++) {
        prefix.push_back(c = ((int)((unsigned)c * 19u) % mod)); // 利用题目中的方法溢出。
        if (m[c]) { // 该数存在过了。
            p = i - m[c]; // 循环节长度就是两数字间的距离。
            b = m[c]; // 开始循环的位置即为 map 里该数字第一次存在的位置。
            break;
        }
        m[c] = i;
    }

    answer.resize(p); // 存放答案。
    _rep(i, 0, p - 1) {
        answer[(i + b) % p] = c;
        c = (int)((unsigned)c * 19u) % mod;
    }
}
// 返回 1_wa998244353 数据的答案。
int solving_modwa(LL x) { return (x < b) ? prefix[x] : answer[x % p]; }

const int prime_list[12] = { 2, 3, 5, 7, 11, 13, (LL) 1e9 + 7 }; // 质数表，用于 Miller-Rabin 算法。

LL gcd(LL a, LL b) { return a % b == 0 ? b : gcd(b, a % b); }

bool miller_rabin(LL x, int times = 7) { // times 控制次数，为 2u 测试点提共方便。
    if (x < 2) // 特判。
        return false;
    if (x == 2 || x == 3 || x == 5 || x == 7)
        return true;
    if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0)
        return false;
    LL cnt = 0, rem = x - 1;
    while (!(rem & 1)) {
        cnt++;
        rem >>= 1;
    }

    _rep(i, 0, times - 1) {
        if(x == prime_list[i]) return true;
        if(x % prime_list[i] == 0) return false;
        LL rt = qpow(prime_list[i], rem, x);
        LL y = rt;
        _rep(i, 1, cnt) {
            rt = qmul(rt, rt, x);
            if (rt == 1 && y != 1 && y != x - 1) {
                return false;
            }
            y = rt;
        }
        if (rt != 1)
            return false;
    }
    return true;
}

void verdict_mobius() {
    int maxn = 1000000;
    vector<int> prime(maxn + 1), v(maxn + 1);
    int m = 0;
    _rep(i, 2, maxn) { // 线性筛。
        if(v[i] == 0) {
            v[i] = i; prime[++m] = i;
        }
        _rep(j, 1, m) {
            if(prime[j] > v[i] || prime[j] > maxn / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
    int t; LL L, R;
    read(t);

    while(t--) {
        read(L); read(R);
        vector<LL> num;
        vector<int> miu;
        num.resize(R - L + 1); miu.resize(R - L + 1);
        _rep(i, 0, R - L) {
            num[i] = 1; miu[i] = 1; 
        }
        _rep(i, 1, m) {
            for(LL j = (((L - 1) / prime[i] + 1) * prime[i]); j <= R; j += prime[i]) { // 在这一段区间内寻找能被该质数整除的数
                int cnt = 0;
                if(j % ((LL) prime[i] * prime[i]) == 0) miu[j - L] = 0; // 如果 j 能被该质数的平方整除，则直接把该数的莫比乌斯函数设为 0 
                else miu[j - L] = -miu[j - L]; // 否则就将莫比乌斯函数乘 -1 
                num[j - L] *= prime[i]; // 乘上该质数。
            }
        }
        _rep(i, 0, R - L) {
            if(miu[i] == 0) {
                putchar('0'); continue;
            } else if(num[i] != i + L) {
                if(miller_rabin((i + L) / num[i], 1)) { // 情况一：剩下这个数是质数。
                    miu[i] *= -1;
                } else {
                    LL t = (long long)sqrt((i + L) / num[i]); // 情况二：剩下这个数是平方数。
                    if(t * t == (i + L) / num[i]) miu[i] = 0;
                }
            }
            putchar(miu[i] == 0? '0' : (miu[i] == 1? '+' : '-'));
        }
        putchar('\n');
    }
}

vector<int> fac[4];
int idx[13126666], vis[13126666];

void factor(int x, int type) { // 质因子分解。
    _rep(i, 2, sqrt(x)) {
        if(x % i == 0) {
            fac[type].push_back(i);
            while(x % i == 0) x /= i;
        }
    }

    if(x > 1) fac[type].push_back(x);
}

bool is_primitive_root(int g, int type, int phi, int mod) { // 判断原根。
    for(auto i : fac[type]) {
        if(qpow(g, phi / i, mod) == 1) return false;
    }
    return true;
}
int main() {
    cin >> utensil;

    if (utensil == "1_998244353") {
        int n;
        read(n);

        _rep(i, 1, n) {
            LL x;
            readmo(x);
            write(qpow(19, x + 998244352, 998244353));
            putchar('\n');
        }
    } else if (utensil == "1?") {
        int n;
        read(n);

        mo = 1145140;
        _rep(i, 1, n) {
            LL x;
            readmo(x);
            write(qpow(19, x + 1145140, 1145141));
            putchar('\n');
        }
    } else if (utensil == "1?+") {
        int n;
        read(n);

        mo = 5211600617818708273ll;
        _rep(i, 1, n) {
            LL x;
            read(x);
            write(qpow(19, x, mo));
            putchar('\n');
        }
    } else if (utensil == "1wa_998244353") {
        int n;
        read(n);

        pretreatment();
        _rep(i, 1, n) {
            LL x;
            read(x);
            write(solving_modwa(x));
            putchar('\n');
        }
    } else if(utensil == "2p") {
        int n;
        read(n);

        _rep(i, 1, n) {
            LL L, R;
            read(L); read(R);
            
            for(long long j = L; j <= R; j++) {
                putchar(miller_rabin(j)? 'p' : '.');
            }
            putchar('\n');
        }    	
    } else if(utensil == "2u") {
        verdict_mobius();
    } else if(utensil == "2g" || utensil == "2g?") {
        int n;
        read(n);

        factor(998244352, 1); // 预处理因子，尽可能减少时间复杂度。
        factor(13123110, 2);
        factor(1515343656, 3);
        _rep(i, 1, n) {
            LL L, R, t, mo;
            string m;
            read(L); read(R);
            cin >> m;

            if(m == "998244353") {
                mo = 998244353; t = 1;
            } else if(m == "13123111") {
                mo = 13123111; t = 2;
            } else {
                mo = 1515343657; t = 3;
            }

            if(t == 2) {
                int g = 6;
                for(auto i : fac[t]) {
                    for(int j = i; j <= mo; j += i) { // 处理所有与 phi(p) 的质因数不互质的数。
                        vis[j] = 1;
                    }
                }

                int ans = 1;
                _rep(i, 1, mo) { // 线性扫指标。
                    ans = ans * g % mo;
                    idx[ans] = i;
                }

                _rep(i, L, R) {
                    putchar(vis[idx[i]] ? '.' : 'g');
                }
                putchar('\n');
            } else {
                _rep(i, L, R) {
                    putchar(is_primitive_root(i, t, mo - 1, mo) ? 'g' : '.');
                }
                putchar('\n');
            }
        }    	
    }
    return 0;
}

题解

测试点 1 ~ 3 : 1_998244353

测试点 4：1?

测试点 5：1?+

测试点 6 ~ 7：1wa_998244353

测试点 8 ~ 10：2p

测试点 11 ~ 13：2u

测试点 14~15：2g，测试点 16：2g?

代码