Description
给出一些测试点的输入文件和输出文件以及每个测试点要实现的功能编号，你需要写一个程序通过这些给出的测试点。
链接，这个题在 loj 上体验很好，洛谷上虽然也有这个题但容易被卡常。
Solution
很明显：功能开头是 $1$ 还是 $2$ 区别很大，我们分开来看。
input1~7
input1~3
这三个点都是 $\text{1\_998244353}$，我们看一下数据。
input：0 1 2 3
output：1 19 361 6859
很明显是要求 $19^n$。
发现肯定有一个模数，那很容易想到就是 $998244353$。
写一个快速幂，这三个点就能过了。
注意第三个点指数很大，根据欧拉定理，我们只需要在读入的时候对 $998244352$ 取模即可。
input4
这个点是 $1?$。
看一下比较小的数据，发现还是求的 $19^n$，而模数不一样了，联想到由 $998244353$ 变成了 $?$，这个点看起来是让我们确定模数。
找到最大的数，发现是 $10^6$ 级别的，且不超过 $2\times10^6$，那我们可以尝试枚举这个模数，判断一下 $19^{627811703016764290815178977207148434322}$ 是否等于 $642666$ 即可。
写了一个 python 代码跑：
def qpow(a, x, p):
res = 1
while x > 0:
if x % 2 == 1:
res = res * a % p
x >>= 1
a = a * a % p
return res
for i in range(10 ** 6, 2 * 10 ** 6):
if qpow(19, 627811703016764290815178977207148434322, i) == 642666:
print('ans', i)
break
#print('check', i)
if i % 10000 == 0:
print(i)
能找到一个模数是 $1145141$，当看到 $114514$ 我们就知道应该是找对了。
模数找到了，这个点还有一个问题：指数太大。
我们看一下 $1145141$ 这个数，写一个判断素数的程序，发现是个质数，且和 $19$ 互质，那么根据欧拉定理，我们只需要在读入的时候对 $1145141-1$ 取模即可。
这个点也就很愉快地搞定了。
input5
实际上这个点可能是整道题最难的一个点了。
这个点是 $1?+$。
联系上一个点，看一下数据，发现似乎还是让我们确定模数，但模数似乎很大很大，最大的答案达到了 $5211500658258874318$，枚举肯定是不行了。
我们想一想怎么样能确定模数。。。
可以想到一个方法：找到两个相邻的指数，根据答案来确定质数。如果不懂就接着往下看。
我们打一个表：
#include <bits/stdc++.h>
using namespace std;
typedef __int128_t lll;
lll read()
{
lll x = 0, f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = getchar())
x = x * 10 + ch - '0';
return x * f;
}
void write(lll x)
{
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline void space() { putchar(' '); }
inline void endln() { putchar('\n'); }
int n = 10000;
const int maxn = 1e4 + 10;
pair<lll, lll> a[maxn];
inline lll myabs(lll x) { return x < 0 ? -x : x; }
int main()
{
lll res = 0;
freopen("tmp5.in", "r", stdin);
for (int i = 1; i <= n; i++)
a[i].first = read();
freopen("software5.ans", "r", stdin);
for (int i = 1; i <= n; i++)
{
a[i].second = read();
//if (myabs(a[i].first - a[i].second) < 10000000000)
// write(a[i].first), putchar(' '), write(a[i].second), putchar('\n');
}
std::sort(a + 1, a + 1 + n);
for (int i = 2; i <= n; i++)
if (a[i].first - a[i - 1].first < 5)
write(a[i - 1].first), space(), write(a[i - 1].second), space(), write(a[i].first), space(), write(a[i].second), endln();
}
/*
5211500658258874318
*/
发现有这么一组数据：
264708066 1996649514996338529
264708068 1589589654696467295
也就是说，设 $1996649514996338529=a,1589589654696467295=b$，有 $19\times19a\equiv b\pmod p$。
那么 $p\mid19\times19a-b=719200885258981741674$，又由于 $p>5211500658258874318$，所以我们只需要枚举一个小于等于 $138$ 的约数就行。
然后拿 python 一算，好家伙，$138$ 正好是一个约数，我们把 $719200885258981741674/138=5211600617818708273$ 这个数放进我们的程序里试一下，它居然过了，真好。
那么这个点也就过了。
以上五个点可以写成一个函数：传入模数，求 $19^n\pmod p$。
input6~7
这两个点给出了模数 $998244353$，但特殊之处在于这个 $\text{wa}$，看一下数据发现出现了负数，再看看题目上的提示，很明显是溢出导致的。
具体是哪里溢出了呢？
首先肯定不是快速幂，你可以试一试，也可以用这个思路去想：每个人的快速幂写法会有差异，不能用这个出题。
那就只剩下暴力一个个乘上去了。。。
试一下，发现貌似是对的。
也就是说在 res = res * 19 % mod 这一步中没开 long long 导致溢出了。
这玩意肯定没法用快速幂算，但是考虑到一个事情：这个溢出相当于对 $2^{32}$ 取模，那么就会产生循环节（因为这个数不是质数，欧拉函数不是它减去 $1$）。
我们可以用 map 来判断循环节，反正循环节应该不是很长：
typedef long long ll;
typedef __int128_t lll;
typedef unsigned int ui;
typedef unsigned long long ull;
int n = 10000;
const int maxn = 1e4 + 10;
const int mod = 998244353;
pair<lll, lll> a[maxn];
inline lll myabs(lll x) { return x < 0 ? -x : x; }
inline int errmul(int a, int b) { return (int)((ui)a * (ui)b); }
map<int, int> mp;
int main()
{
int now = 1;
mp[0] = 1;
for (int i = 1; ; i++)
{
now = errmul(now, 19) % mod;
if (mp.count(now))
{
cout << i << " " << mp[now] << " " << i - mp[now] << " " << now << endl;
return 0;
}
mp[now] = i;
}
}
然后找到循环节开始位置是 $55245$，长度是 $45699$。
对于这两个点，直接暴力找循环节，对于一个询问，直接小学数学取个模就行。
那么这前 $7$ 个点就过了，$41$ 分到手。
input8~16
这些点都有一个共同特征：给一个区间，问区间内所有数的一些性质。
分开来看三种功能：
input8~10
这三个点的关键信息是 $\text{p}$，看一下小数据：
input：2 10
output：pp.p.p...
很明显了吧，是求区间内所有质数。
发现数是非常大的，但区间不大，只有 $10^6$ 级别。
那我们直接对每个区间内的所有数进行 Miller-Rabin 素性测试就行了。
我一般找 $10$ 个随机数测试，但本机速度有点慢，跑不过去，于是进行了一波卡常：不使用随机数，而是用固定的数来测试（因为这样可以减少测试次数）。
试了试发现好像只用 $2,3$ 检测就能过这三个点，那就这样吧。
后来我又试了试随机数的判定，不知道为什么，在 loj 跑 $10$ 个随机数仍然飞快（第 $10$ 个点 232ms），但在洛谷跑 $5$ 个随机数就很勉强（第 $10$ 个点 1.39s），所以还是建议大家去 loj 做，避免卡常（）
input11~13
关键信息是 $\text{u}$，这是啥呢？
看一看答案，发现只有三种：负号、正号、零。
这。。再看看小数据联想一下，应该是莫比乌斯函数。
和上一个功能一样，数非常大，区间不大。
有一个比较经典的题是区间筛素数，使用的方法是先筛出平方根范围内的素数，然后再筛那个区间里的素数。
我们可以尝试类似的思路。
先筛出 $(10^{18})^{1/3}=10^6$ 范围内的素数以及莫比乌斯函数，用这些数去筛指定区间内的莫比乌斯函数，即让每个数都除掉他们在 $[1,10^6]$ 范围内的质因子，同时更新莫比乌斯函数。
这样剩下的数有一些很好的性质：要么是素数，要么是两个大于 $10^6$ 素数的积。
那么接下来的事情就比较明了了：
- 用 Miller-Rabin 先判断剩下的数是不是素数，如果是，那么把答案取相反数；
- 如果不是素数，我们判断这个数是不是平方数，如果是，答案变为 $0$；
- 如果都不是，那么就是由两个不同素数乘起来得到的，这样答案不变。
写出来之后在我的机子上又跑不过去了，想办法剪剪枝卡常：
- 多筛一些质数，能减少 Miller-Rabin 的执行次数；
- 很显然，如果答案已经是 $0$，不用管；
- 如果剩下的数是 $1$，不用管；
折腾完之后在我的机子上看起来速度还行，loj 上飞快。
这三个点也就过了。
input14~16
关键信息是 $\text{g}$，有了刚刚的经验，这个东西应该也是一个数学符号。
想一想再看看数据能发现是判断一个数是否是指定数的原根。
首先有原根判定定理：设 $m \geqslant 3, \gcd(a,m)=1$，则 $a$ 是模 $m$ 的原根的充要条件是，对于 $\varphi(m)$ 的每个素因数 $p$，都有 $a^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m$。
对于 input14，模数全部是 $998244353$，$\varphi(998244353)=998244352$ 质因子只有 $2,7,17$，区间也不大，直接暴力判断即可。
对于 input15，有一个模数是 $13123111$，$\varphi(13123111)=13123110=2\times3\times5\times7\times11\times13\times19\times23$，区间还贼大，暴力判断看上去不太行。
得请出另一个结论了：若 $\gcd\big(k,\varphi(m)\big)=1$，则有：$\delta_m(g^k)=\varphi(m)$，即 $g^k$ 也是模 $m$ 的原根。
用这个就可以筛原根了。
接着是最后一个点 input16，这个点有一个 $10^9\sim2\times10^9$ 的质数作为模数需要我们确定，我们使用 input14 的思路暴力枚举这个质数，然后暴力分解质因数来判断原根情况和原来是否一致即可。我这里只检验了前 $49$ 位。
看起来很暴力，但因为素数并不是特别多而且很容易检测出问题，实际代码跑起来是很快的。
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned int ui;
typedef unsigned long long ull;
ll qpow(ll a, ll x, ll p)
{
ll res = 1;
for (; x; x >>= 1, a = (lll)a * a % p)
if (x & 1)
res = (lll)res * a % p;
return res;
}
bool MR(ll n)
{
if (n < 3 || n % 2 == 0)
return n == 2;
if (n == 3 || n == 5 || n == 7 || n == 11)
return 1;
if (n % 3 == 0)
return n == 3;
ll a = n - 1, b = 0;
while (a % 2 == 0)
a >>= 1, b++;
for (int i = 0, j; i < 5; i++)
{
ll c = rand() % (n - 1) + 1;
ll v = qpow(c, a, n);
if (v == 1)
continue;
for (j = 0; j < b; j++)
{
if (v == n - 1)
break;
v = (lll)v * v % n;
}
if (j >= b)
return false;
}
return true;
}
char s[100];
std::vector<int> a;
int n, m;
int check(int x)
{
a.clear();
int t = x - 1;
for (int i = 2; i * i <= t; i++)
{
if (t % i == 0)
{
a.push_back(i);
while (t % i == 0)
t /= i;
}
}
int q = x - 1;
for (int i = 1; i <= 49; i++)
{
int now = i + n - 1;
int ok = 1;
for (int j : a)
if (qpow(now, q / j, x) == 1)
{
ok = 0;
break;
}
if (ok && s[i] == '.')
return false;
else if (!ok && s[i] == 'g')
return false;
}
return true;
}
int main()
{
int l, r;
cin >> l >> r;
freopen("in.in", "r", stdin);
cin >> n >> m;
cin >> (s + 1);
for (int i = l; i <= r; i++)
{
if (!MR(i))
continue;
int flag = check(i);
if (flag == 1)
cout << i << endl;
}
}
我这里采用 $10$ 个程序并行的方式进行计算，效率很高，我刚开始第六个程序，第一个程序就跑完了。
找出来合法的数只有一个：$1515343657$。质因数分解一下 $1515343656$，发现质因子是 $2,3,4003,15773$，区间不大，直接用 input14 的方法暴力判断即可。
这样这道题就做完了。
Code
完全没压行，所以很长。
明明实际上挺码农的但写起来不感觉码农，也说明这道题挺有意思的。
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned int ui;
typedef unsigned long long ull;
namespace IO
{
const int mxsiz = 1 << 20;
char inbuf[mxsiz], *p1, *p2;
char outbuf[mxsiz], *op = outbuf;
struct endio
{
endio(){};
~endio() { fwrite(outbuf, 1, op - outbuf, stdout); }
} useless_var;
inline char gc() { return p1 == p2 && (p2 = (p1 = inbuf) + fread(inbuf, 1, mxsiz, stdin), p1 == p2) ? EOF : *p1++; }
#define isdigit(x) (x >= '0' && x <= '9')
inline ll read()
{
ll x = 0, f = 1;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = gc())
x = x * 10 + ch - '0';
return x * f;
}
int read_mod(int p)
{
int x = 0, f = 1;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = gc())
x = (lll)x * 10 % p + ch - '0', x %= p;
return x * f;
}
#undef isdigit
inline void push(char ch)
{
if (op - outbuf == mxsiz)
fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
*op++ = ch;
}
template <typename T>
inline void work_wt(T x)
{
if (x > 9)
work_wt(x / 10);
push(x % 10 + '0');
}
template <typename T>
inline void write(T x)
{
if (x < 0)
x = -x, push('-');
work_wt(x);
}
inline void endln() { push('\n'); }
inline void space() { push(' '); }
template <typename T>
inline void writeln(T x) { write(x), endln(); }
}
using namespace IO;
ll qpow(ll a, ll x, ll p)
{
ll res = 1;
for (; x; x >>= 1, a = (lll)a * a % p)
if (x & 1)
res = (lll)res * a % p;
return res;
}
namespace task1
{
int n;
void solve(const ll mod = 998244353)
{
n = read();
for (int i = 1; i <= n; i++)
write(qpow(19, read_mod(mod - 1), mod)), endln();
}
std::map<int, int> mp;
inline int errmul(int a, int b) { return (int)((ui)a * (ui)b); }
void solve2()
{
const int begin = 55245, round = 45699;
const int mod = 998244353;
mp[0] = 1;
int now = 1;
for (int i = 1; i <= begin + round; i++)
{
now = errmul(now, 19) % mod;
mp[i] = now;
}
n = read();
for (int i = 1; i <= n; i++)
{
ll x = read();
write(x <= begin ? mp[x] : mp[(x - begin) % round + begin]);
endln();
}
}
}
bool MR(ll n)
{
if (n < 3 || n % 2 == 0)
return n == 2;
if (n == 3 || n == 5 || n == 7 || n == 11)
return 1;
ll a = n - 1, b = 0;
while (a % 2 == 0)
a >>= 1, b++;
for (int i = 0, j; i < 2; i++)
{
ll c;
if (i == 0)
c = 2;
else if (i == 1)
c = 3;
ll v = qpow(c, a, n);
if (v == 1)
continue;
for (j = 0; j < b; j++)
{
if (v == n - 1)
break;
v = (lll)v * v % n;
}
if (j >= b)
return false;
}
return true;
}
namespace task2
{
void solve()
{
int n = read();
while (n--)
{
ll l = read(), r = read();
for (ll i = l; i <= r; i++)
push(MR(i) ? 'p' : '.');
endln();
}
}
}
namespace task3
{
const int maxn = 5e6 + 10;
int mu[maxn], pri[maxn], vis[maxn], tot;
void init(const int n = 5e6)
{
mu[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
pri[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * pri[j] <= n; j++)
{
vis[i * pri[j]] = 1;
if (i % pri[j] == 0)
{
mu[i * pri[j]] = 0;
break;
}
else
mu[i * pri[j]] = -mu[i];
}
}
}
int ans[maxn];
ll now[maxn];
inline bool check(ll x)
{
ll p = std::sqrt(x);
return p * p == x;
}
void work(ll x, ll y)
{
if (y <= 5e6)
{
for (int i = x; i <= y; i++)
if (mu[i] == 0)
push('0');
else if (mu[i] == 1)
push('+');
else if (mu[i] == -1)
push('-');
}
else
{
for (int i = 0; i <= y - x; i++)
now[i] = i + x;
memset(ans, 1, sizeof(ans));
for (int i = 1; i <= tot; i++)
{
int p = pri[i];
ll j = 1ll * x / p;
ll pos = 1ll * j * p;
while (pos < x)
pos += p;
while (pos <= y)
{
int rp = pos - x;
int cnt = 0;
while (now[rp] % p == 0)
now[rp] /= p, cnt++;
if (cnt > 1)
ans[rp] = 0;
else if (ans[rp] > 1)
ans[rp] = -1;
else
ans[rp] *= -1;
pos += p;
}
}
for (int i = 0; i <= y - x; i++)
{
if (ans[i] == 0 || now[i] == 1)
continue;
if (MR(now[i]))
ans[i] = ans[i] > 2 ? -1 : ans[i] * -1;
else if (now[i] != 1 && check(now[i]))
ans[i] = 0;
else if (ans[i] > 2)
ans[i] = 1;
}
for (int i = 0; i <= y - x; i++)
if (ans[i] == 0)
push('0');
else if (ans[i] == 1)
push('+');
else if (ans[i] == -1)
push('-');
}
}
void solve()
{
init();
int n = read();
for (ll x, y, i = 1; i <= n; i++)
x = read(), y = read(), work(x, y), endln();
}
}
std::string s;
namespace task4
{
int n;
const int maxn = 1.4e7 + 10;
bool ans[maxn];
void BF(int l, int r, int p)
{
int q = p - 1;
for (int i = l; i <= r; i++)
{
if (qpow(i, q / 2, p) == 1 || qpow(i, q / 7, p) == 1 || qpow(i, q / 17, p) == 1)
ans[i - l] = 0;
else
ans[i - l] = 1;
}
for (int i = 0; i <= r - l; i++)
push(ans[i] ? 'g' : '.');
endln();
}
void BF2(int l, int r, int p)
{
int q = p - 1;
for (int i = l; i <= r; i++)
{
if (qpow(i, q / 2, p) == 1 || qpow(i, q / 3, p) == 1 || qpow(i, q / 4003, p) == 1
|| qpow(i, q / 15773, p) == 1)
ans[i - l] = 0;
else
ans[i - l] = 1;
}
for (int i = 0; i <= r - l; i++)
push(ans[i] ? 'g' : '.');
endln();
}
const int g = 6;
inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
void qwq(int l, int r, int p)
{
const int q = p - 1;
int now = g;
for (int i = 1; i <= r; i++)
{
if (gcd(i, q) == 1)
{
ans[now] = 1;
}
now = now * g % p;
}
for (int i = l; i <= r; i++)
push(ans[i] ? 'g' : '.');
endln();
}
void work(int l, int r, int p)
{
if (p == 998244353)
BF(l, r, p);
else if (p == 1515343657)
BF2(l, r, 1515343657);
else
qwq(l, r, p);
}
void solve(int flag = 0)
{
n = read();
for (int i = 1; i <= n; i++)
{
int x = read(), y = read();
if (flag && i == n)
work(x, y, 1515343657);
else
work(x, y, read());
memset(ans, 0, sizeof(ans));
}
}
}
int main()
{
cin >> s;
if (s == "1_998244353")
task1::solve();
else if (s == "1?")
task1::solve(1145141);
else if (s == "1?+")
task1::solve(5211600617818708273);
else if (s == "1wa_998244353")
task1::solve2();
else if (s == "2p")
task2::solve();
else if (s == "2u")
task3::solve();
else if (s == "2g")
task4::solve();
else if (s == "2g?")
task4::solve(1);
}