构造 + 费马小定理
2022ICPC网络赛（II）A
[题目详情 - A Yet Another Remainder (pintia.cn)](https://codeforces.com/contest/1734/problem/E)
题意
有一个大整数 \(x(1<=x<=10^{10^6})\), 给出 \(x\) 的十进制位数为 \(n(1<=n<=10^6)\), 设从高到低位的数为 \(a[i](1<=i<=n)\), 并给出 \(min(n,100)\) 行信息 \(b_{i,j}\)，第 \(i\) 行有 \(i\) 个数，
\(b_{i,j}\) 表示 for (int k = j; k <= n; k += i) b[i][j] += a[i];
有 \(q(1<=q<=10)\) 组询问，每组给出一个素数 \(p\;(p=3\;or\;7<=p<=97)\), 求 \(x\mod p\) 的结果
思路
-
首先关于同余的题目，最好下标从 0 开始，因此先把题干下标由低位到高位是 \([n,1]\) 改成从低位到高位分别是 \([0,n-1]\), 把 \(b_{i,j}\) 预处理一下
-
再思考 \(b_{i,j}\) 是什么含义，\(b_{i,j}\) 其实是 \(a\) 数组的下标，在模 \(i\) 意义下，同余于 \(j\) 的所有数之和
-
肯定不会是让把 \(a[i]\) 全部求出来，很可能是要通过 \(b_{i,j}\) 把 \(x\) 拼出来
-
由于答案并非求 \(x\), 而是求 \(x \mod p\) 的值，就转化为找一个较好拼凑出的 \(y\), 满足 \(y\equiv x\pmod p\)
-
\(x=1*a_0+10*a_1+100*a_2+...+10^i*a_i+...+10^n*a_n\)
通过暴力验证可以发现，对于任何一个素数 \(p\;(p=3\;or\;7<=p<=97)\)，都能在 100 以内找到一个 \(i\), 使得 \(10^i\equiv 1\pmod p\)
(这里其实用费马小定理就可以，\(i=p-1\))
因此 \(x\equiv (a_0+10*a_1+...+10^{i-1}a_{i-1})+(a_i+10*a_{i+1}+...+10^{i-1}*a_{2*i-1})+...+\)
用 b矩阵的第 \(i\) 行乘相应的系数就可拼凑出上式
- n 较小时可能不存在第 \(i(即p-1)\) 行, 要暴力特判
代码
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) x.size()
typedef long long ll;
inline ll _read() {
static ll ans;
static unsigned int c;
static bool p;
for (c = getchar(); c != '-' && (c < '0' || c > '9'); c = getchar());
if (c == '-') p = false, c = getchar(); else p = true;
for (ans = 0; c <= '9' && c >= '0'; c = getchar()) ans = ans * 10 + c - '0';
return p ? ans : -ans;
}
const int N = 110;
int pr[N], cnt;
bool st[N];
void get_primes(int n)
{
memset(st, true, sizeof st);
st[1] = false;
for (int i = 2; i <= n; i++)
{
if (st[i])
pr[++cnt] = i;
for (int j = 1; j <= cnt && pr[j] <= n / i; j++)
{
int p = pr[j];
st[i * p] = false;
if (i % p == 0)
break;
}
}
}
ll qmi(ll a, ll b, ll p)
{
ll ans = 1;
while(b)
{
if (b & 1)
ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans % p;
}
int id[N];
void presolve()
{
for (int j = 1; j <= cnt; j++)
{
int p = pr[j];
for (int i = 1; i <= 99; i++)
{
if (qmi(10, i, p) == 1)
{
id[p] = i;
break;
}
}
}
}
ll b[N][N];
int n, q;
int p;
ll solve()
{
p = _read();
int len = id[p];
ll ans = 0;
for (int i = 0; i < len; i++)
{
ans += b[len][i] * qmi(10, i, p) % p;
if (ans >= p)
ans -= p;
}
return ans;
}
void solve2()
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
b[i][j] = _read();
}
q = _read();
while(q--)
{
p = _read();
ll ans = 0;
for (int i = 0; i < n; i++)
{
ans += qmi(10, n - i - 1, p) * b[n][i] % p;
if (ans >= p)
ans -= p;
}
printf("%lld\n", ans);
}
}
int main() {
get_primes(99);
presolve();
int T = _read();
while(T--)
{
n = _read();
if (n <= 100)
{
solve2();
continue;
}
for (int i = 1; i <= 100; i++)
{
for (int j = 0; j < i; j++)
{
int jj = j + 1;
int r = (n - jj) / i * i + jj - 1;
r = n - 1 - r;
b[i][r] = _read();
}
}
q = _read();
while(q--)
{
ll ans = solve();
printf("%lld\n", ans);
}
}
return 0;
}