P5285 [十二省联考 2019] 骗分过样例
题目链接
前言
一道很考验数论水平、耐心与注意力的题
\(16\) 个测试点中有 \(14\) 个是我独立完成的,剩余的测试点 #7,#13 分别参考了题解和讨论区
题目大意
下发 \(16\) 组测试数据,推断每组数据的题意并完成对应题目
前置知识
大家应该都会的
快速幂
高精度
数论基础
费马小定理/欧拉定理
筛法求素数
大家可能不会的
莫比乌斯函数
miller_rabin
原根
解法
Part.1 #1~7
这 \(7\) 个点求的是 \(19^x\) 在不同情况下的值
#1 1_998244353(4pts)
模数为 \(998244353\),此数据点数据较小,可使用快速幂或暴力
#2 1_998244353(4pts)
所求的数同上,但 \(x\) 的范围加大,需要使用快速幂
#3 1_998244353(4pts)
\(x\) 的范围再一次加大,达到了 \(10^{39}\) 以上,即使 __int128
也无法直接存储,需要使用费马小定理或欧拉定理,将模数对 \(998244352\) 取模
#4 1?(7pts)
模数未知,但可以发现模数不太大,由模数大于取模结果的最大值,打表时暴力枚举模数即可得出模数为 \(1145141\)
其实看到最大值形如 \(1145...\) 就应当推测出模数的前六位(
#5 1?+(9pts)
模数依然未知,但达到了 \(10^{18}\) 的数量级,显然不能暴力枚举
注意到同余的性质:若 $a \equiv b \pmod m $,则 $m\mid(a-b) $
则 \(m \mid 19^k-(19^k\bmod m)\),打表时多取几组不同的 \(k\)(我在代码中取了最小的三组),求高精度 \(\gcd\) 即可发现模数是 \(5211600617818708273\)
#6 1wa_998244353(6pts)
观察到输出了负数,由功能标号中的“wa”不难得出这一组是不开 long long
导致溢出后的错误结果,数据较小,对 int
类型数暴力乘即可
#7 1wa_998244353(7pts)
👿
数据较上一问更大,不能使用暴力,但快速幂又会输出错误结果
通过强大的注意力观察题解可知该结果具有较短的循环节,打表时得出从 \(k=45699\) 开始每 \(55245\) 为一循环
Part.2-1 #8~10
p
来源于 prime(质数)
这 \(3\) 个点是筛区间 \([l,r]\) 中的质数,是质数则输出 p
,否则输出 .
#8 2p(4pts)
数据很小,仅到 \(10^6\),暴力筛即可
#9 2p(6pts)
数据范围达到了 \(10^{12}\)
注意到任何一个合数 \(a\) 的最小质因数必定不大于 \(\sqrt a\),则只需预处理 \([1,10^6]\) 中的质数,用这些质数 去筛即可
#10 2p(8pts)
数据范围达到了 \(10^{18}\),即使开平方也有 \(10^9\),无法直接筛质数
但是只使用 miller_rabin 算法判断质数不一定能通过
可以先用 \(10^6\) 以内的质数筛,筛出来可能为质数的数再用 miller_rabin 检验
Part.2-2 #11~13
u
来源于 \(\mu\)(莫比乌斯函数)
这 \(3\) 个点是求区间 \([l,r]\) 中的莫比乌斯函数,为 \(1\) 时输出 +
,为 \(-1\) 时输出 -
,为 \(0\) 时输出 0
#11 2u(5pts)
同#8
#12 2u(6pts)
同#9
#13 2u(9pts)
👿
数据范围达到了 \(10^{18}\)
先判断平方因子,再用 \(10^6\) 以内的质数筛,筛完以后剩下的数只有三种可能:
- \(p(p\in \mathbb{P})\)
- \(pq(p,q\in \mathbb{P})\)
- \(p^2(p\in \mathbb{P})\)
情况三开平方并特判,然后通过 miller_rabin 确定属于情况一还是二
但此时会得到 TLE,原因是 miller_rabin 耗时过大
最玄学的一步:首先多筛一些质数,然后将 miller_rabin 的判断次数改为 \(1\),就可以卡过去并且AC了
我知道 miller_rabin 只判断一次很逆天,但它真的能AC
Part.2-3 #14~16
g
指原根
这 \(3\) 个点是判断区间 \([l,r]\) 中的原根,是原根则输出 g
,否则输出 .
·
#14 2g(5pts)
模数均为 \(998244353\),直接按照原根判定定理暴力判断即可
#15 2g(7pts)
模数为 \(13123111\),但区间为 \([1,13123110]\),按照原根判定定理判断会 TLE,可以暴力枚举原根 \(6\) 的次幂,幂次与 \(13123110\) 互质时即为原根
判断互质时直接用 __gcd
会 TLE,需要先将 \(13123110\) 分解质因数,再用质因数筛去不可行的幂次
#16 2g?(9pts)
模数未知,但提示了模数是 \([10^9,2\times10^9]\) 之间的质数,打表时暴力枚举每一个质数即可得出模数为 \(1515343657\),然后再暴力判断原根
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define P putchar_unlocked
#define Endl putchar_unlocked('\n')
using namespace std;const string Op[8] = {"1_998244353","1?","1?+","1wa_998244353","2p","2u","2g","2g?"};
string op;
int n;const int md[5] = {998244353,1145141,5211600617818708273ll,13123111,1515343657};
// __int128下的快速幂
int qpow128(__int128 x , int y , int mod){__int128 res = 1;while(y){if(y & 1) res = res * x % mod;x = x * x % mod , y >>= 1;}return (int)res;
}
// 1_998244353 , 1? , 1?+
void f1(int type){while(n--){string str; cin>>str;int x = 0;for(int i = 0; i < (int)str.length(); ++i)x = (x * 10 + str[i] - '0') % (md[type] - 1);cout<<qpow128(19 , x , md[type])<<'\n';}
}const int Len = 45699 , Beg = 55245 , M_ = 1.1e5;
signed wa[M_];
// 1wa_998244353
void f1wa(){wa[0] = 1;for(int i = 1; i < M_; ++i) wa[i] = wa[i - 1] * 19 % md[0];while(n--){int x; cin>>x;cout<<wa[x <= Beg ? x : (x - Beg) % Len + Beg]<<'\n';}
}const int p0[1] = {2};
bool miller_rabin(int x){if(x < 4) return x >> 1;int x_ = x - 1 , t = 0;while(!(x_ & 1)) x_ >>= 1 , ++t;for(int i = 0; i < Mp0; ++i){if(p0[i] == x) return 1;int a = p0[i] % x;if(a == 1 || a + 1 == x) continue;a = qpow128(a , x_ , x);if(a == 1 || a + 1 == x) continue;for(int i = 0; i < t - 1; ++i){a = (__int128)a * a % x;if(a + 1 == x) break;}if(a + 1 != x) return 0;}return 1;
}const int M = 1e7 , N = 1e6+5;
int pr[N] , cnt , mu[N] , num[N];
bitset<M> npr;
// 预处理质数
void getprime(){npr[0] = npr[1] = 1;for(int i = 2; i < M; ++i){if(npr[i]) continue;pr[cnt++] = i;for(int j = 2; i * j < M; ++j) npr[i * j] = 1;}
}bitset<N> sq;
// 2p
void f2p(){getprime();while(n--){sq.reset();int l , r , d;cin>>l>>r , d = r - l;for(int i = 0; i < cnt; ++i){int b = (pr[i] - l % pr[i]) % pr[i];for(int j = 0; pr[i] * j + b <= d; ++j) sq[pr[i] * j + b] = 1;}for(int i = 0; i <= d; ++i){if(i + l < M) P(npr[i + l] ? '.' : 'p');else if(sq[i]) P('.');else P(miller_rabin(i + l) ? 'p' : '.');}Endl;}
}
// 2u
void f2u(){getprime();while(n--){memset(mu , 0 , sizeof(mu));sq.reset();int l , r , d;cin>>l>>r , d = r - l;for(int i = 0; i <= d; ++i) num[i] = i + l;for(int i = 0; i < cnt; ++i){int p_ = pr[i] * pr[i] , b = (p_ - l % p_) % p_;for(int j = 0; p_ * j + b <= d; ++j) sq[p_ * j + b] = 1;}for(int i = 0; i < cnt; ++i){int b = (pr[i] - l % pr[i]) % pr[i];for(int j = 0; pr[i] * j + b <= d; ++j){int u = pr[i] * j + b;mu[u] ^= 1 , num[u] /= pr[i];}}for(int i = 0; i <= d; ++i){if(sq[i]) P('0');else{if(num[i] != 1){int sq = sqrtl(num[i]);if(sq * sq == num[i]){ P('0'); continue; }mu[i] ^= miller_rabin(num[i]);}P(mu[i] ? '-' : '+');}}Endl;}
}// long long下的快速幂
int qpow(int x , int y , int mod){int res = 1;while(y){if(y & 1) res = res * x % mod;x = x * x % mod , y >>= 1;}return res;
}bitset<13124000> root , av;
int mod , dv[20] , dvn;
// 分解质因数
void divide(int x){dvn = 0;for(int i = 0; pr[i] * pr[i] <= x; ++i){if(x % pr[i] == 0){dv[dvn++] = pr[i];while(x % pr[i] == 0) x /= pr[i];}}if(x != 1) dv[dvn++] = x;
}
// 判断原根
int checkroot(int x){if(mod == md[3]) return root[x];for(int i = 0; i < dvn; ++i) if(qpow(x , (mod - 1) / dv[i] , mod) == 1) return 0; return 1;
}// 预处理13123111的原根
void getmod3(){for(int i = 0; i < dvn; ++i) for(int j = 1; dv[i] * j < md[3]; ++j) av[dv[i] * j] = 1;for(int i = 1 , p = 6; i < md[3]; ++i , (p *= 6) %= md[3]) if(!av[i]) root[p] = 1;
}
// 2g
void f2g(){getprime();divide(md[3] - 1) , getmod3();while(n--){int l , r; string str;cin>>l>>r>>str;mod = md[str == "13123111" ? 3 : (str == "?" ? 4 : 0)];divide(mod - 1);for(int i = l; i <= r; ++i) P(checkroot(i) ? 'g' : '.');Endl;}
}signed main(){ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);cin>>op>>n;if(op == Op[0]) f1(0);if(op == Op[1]) f1(1);if(op == Op[2]) f1(2);if(op == Op[3]) f1wa();if(op == Op[4]) f2p();if(op == Op[5]) f2u();if(op == Op[6]) f2g();if(op == Op[7]) f2g();return 0;
}
// Enjoy the number theory :)
后记
做这道题感觉收获满满,把测试点逐个击破的感觉很艰辛但也很爽
强烈建议所有人来做这道题👿