(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
十分奇怪的一道题,不过其中涉及到的很多知识点却又是很实用的。
题意描述的已经很清楚了,这里对于每类点分别写一个 namespace
并分别讲解。
这些是本题很多地方需要用到的一些函数,这里我把它们封装到一起:
xxxxxxxxxx
721namespace Default{
2 mt19937 rnd(random_device{}());
3 int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
4 template<typename T = int>
5 inline T read(void){
6 T ret(0);
7 short flag(1);
8 char c = getchar();
9 while(c != '-' && !isdigit(c))c = getchar();
10 if(c == '-')flag = -1, c = getchar();
11 while(isdigit(c)){
12 ret *= 10;
13 ret += int(c - '0');
14 c = getchar();
15 }
16 ret *= flag;
17 return ret;
18 }
19 ll readBignum(ll MOD){
20 ll ret(0);
21 char c = getchar();
22 while(!isdigit(c))c = getchar();
23 while(isdigit(c)){
24 ret = (ret * 10 + int(c - '0')) % MOD;
25 c = getchar();
26 }
27 return ret;
28 }
29 ll readBignum(ll MOD, string num){
30 ll ret(0);
31 for(auto c : num){
32 if(!isdigit(c))continue;
33 ret = (ret * 10 + int(c - '0')) % MOD;
34 }
35 return ret;
36 }
37 ll qmul(ll x, ll y, ll MOD){
38 return (__int128_t)x * y % MOD;
39 // ll quot = (ld)x / MOD * y;
40 // ll ret = (unll)x * y - (unll)quot * MOD;
41 // return (ret + MOD) % MOD;
42 }
43 ll qpow(ll a, ll b, ll MOD){
44 ll ret(1), mul(a);
45 while(b){
46 if(b & 1)ret = qmul(ret, mul, MOD);
47 b >>= 1;
48 mul = qmul(mul, mul, MOD);
49 }
50 return ret;
51 }
52 bool MillerRabin(ll n, bool special = false){
53 int prime[20] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
54 if(n % 2 == 0 || n <= 2)return n == 2;
55 ll power(n - 1); int cnt(0);
56 while(power % 2 == 0)power /= 2, ++cnt;
57 int times = special ? 1 : 12;
58 while(times--){
59 if(n == prime[times + 1])return true;
60 ll base = prime[times + 1], res = qpow(base, power, n);
61 ll nxt;
62 // if(res == n - 1 || res == 1)continue;
63 for(int i = 1; i <= cnt; ++i){
64 nxt = qmul(res, res, n);
65 if(nxt == 1 && res != 1 && res != n - 1)return false;
66 res = nxt;
67 }
68 if(nxt != 1)return false;
69 }
70 return true;
71 }
72}
下面对这些函数的作用进行简单说明:
xxxxxxxxxx
21mt19937 rnd(random_device{}());
2int rndd(int l, int r);
随机数生成器。
xxxxxxxxxx
21template<typename T>
2inline T read(void);
标准的快读模板。
xxxxxxxxxx
21ll readBignum(ll MOD);
2ll readBignum(ll MOD, string num);
读入一些特别长的数,并在读入过程中取模。
xxxxxxxxxx
11ll qpow(ll a, ll b, ll MOD);
快速幂模板。
xxxxxxxxxx
11ll smul(ll x, ll y, ll MOD);
快速乘模板,用 __int128_t
实现。
xxxxxxxxxx
11bool MillerRabin(ll n, bool special = false);
用于快速判定是否为素数,关于 Miller Rabin。
简单观察发现输入为
输出为
显然为
所以显然这个功能即为输入
然后观察文件名发现其中有 998244353
字段,十分显然就是对其取模,即求的是
对于前两个点简单的快速幂就能过,而对于第三个点发现
若
为素数,则有 。
简单转化一下,令
所以对于这三个点丢可以直接输出
同时发现 long long
了,于是我们需要在读入的时候边读入边取模。
xxxxxxxxxx
91namespace Case_1_2_3{
2 void Make(ll MOD = 998244353){
3 int N = Default::read();
4 for(int i = 1; i <= N; ++i){
5 ll x = Default::readBignum(MOD - 1);
6 printf("%lld\n", Default::qpow(19, x, MOD));
7 }
8 }
9}
观察文件名发现,区别只是模数变成了 ?
,于是这也很显然,我们需要确定模数。
观察样例,我们发现以下几个性质:
于是写出枚举找素数的程序:
xxxxxxxxxx
151namespace Case_4{
2 ll FindMod(void){
3 string val_s("627811703016764290815178977207148434322");
4 ll std_res = 642666;
5 for(ll i = 1145099 + 1; i <= LLONG_MAX; ++i){
6 if(i % 2 == 0 || !Default::MillerRabin(i))continue;
7 ll val = Default::readBignum(i - 1, val_s);
8 ll res = Default::qpow(19, val, i);
9 if(res == std_res)return i;
10 }
11 }
12 void Make(void){
13 Case_1_2_3::Make(1145141ll);
14 }
15}
跑一下就可以得到素数为
既然是升级版肯定不会让你这么简单枚举出来模数的
有一个很人类智慧的枚举方法,对于整个输入输出,我们要找到一对最接近的
这时简单想一下就会发现可以通过
或者写成:
所以显然这个时候我们需要枚举的模数就只可能是
思路大概这样,实现就不写了,只需要注意两个点:
long long
范围内,我们也只需要在此范围内枚举。总之最后得出来的结果应该是:
模数是
xxxxxxxxxx
51namespace Case_5{
2 void Make(void){
3 Case_1_2_3::Make(5211600617818708273ll);
4 }
5}
观察文件名发现序号没变,那么求的东西不变,然后观察文件名里有 wa
,输出的答案里有负数,又联想到提示里的内容,所以显然这个是因为 int
溢出了所以变成负数。
然后我们感性理解一下,模意义下的很多模数都是一个群,从群的角度感性理解一下这个溢出应该也会有周期性,所以我们可以通过 map < int, int >
来找第一个重复出现的数,也就是周期。
大概的实现是这样:
xxxxxxxxxx
231namespace Case_6_7{
2 const int MOD(998244353);
3 int ans[11000000];
4 int beg(-1), siz(-1);
5 void FindCirc(void){
6 map < int, int > mp;
7 int base(1);
8 mp.insert({ans[0] = base, 0});
9 for(int i = 1; true; ++i){
10 if(mp.find(base = signed((unsigned)base * (unsigned)19) % MOD) != mp.end()){beg = mp[base], siz = i - mp[base]; return;}
11 else mp.insert({ans[i] = base, i});
12 }
13 }
14 void Make(void){
15 FindCirc();
16 int N = Default::read();
17 for(int i = 1; i <= N; ++i){
18 ll x = Default::read<ll>();
19 if(x < beg)printf("%d\n", ans[x]);
20 else printf("%d\n", ans[(x - beg) % siz + beg]);
21 }
22 }
23}
序号变为 p
显然代表着 Prime,简单看一下样例就能明白要实现的是对于 p
,合数输出 .
,简单用 Miller-Rabin 判一下即可。
xxxxxxxxxx
121namespace Case_8_9_10{
2 void Make(void){
3 int N = Default::read();
4 for(int i = 1; i <= N; ++i){
5 ll l = Default::read<ll>(), r = Default::read<ll>();
6 for(ll x = l; x <= r; ++x){
7 printf("%c", Default::MillerRabin(x) ? 'p' : '.');
8 }
9 printf("\n");
10 }
11 }
12}
观察文件名 u
显然是求莫比乌斯函数,对于第一个点显然打个线性筛就行,具体看这里。
第二第三个点可以理解为求任意区间内的莫比乌斯函数,可以考虑把值域分一下,预处理出 相信你们都会。
然后显然对于区间内最后剩下的数一定是一下几个情况:
这里如果
不过这题 Luogu 上卡常很离谱, 通过面向数据剪枝我们可以发现如果把求莫比乌斯函数时候的 Miller-Rabin 测试次数设置为 刚好可以把数据卡过不影响正确性,于是可以卡常过 Luogu,在 LOJ 上评测机比较快可以不用考虑这一点。
xxxxxxxxxx
581namespace Case_11_12_13{
2
3
4 void Make(void){
5 vector < int > prime;
6 bool vis[PRE + 10];
7 int mu[PRE + 10];
8 vis[1] = true, mu[1] = 1;
9 for(int i = 2; i <= PRE; ++i){
10 if(!vis[i]){
11 vis[i] = true;
12 mu[i] = -1;
13 prime.push_back(i);
14 }
15 for(auto p : prime){
16 if(p * i > PRE)break;
17 vis[p * i] = true;
18 mu[p * i] = i % p == 0 ? 0 : -mu[i];
19 if(i % p == 0)break;
20 }
21 }
22 int N = Default::read();
23 while(N--){
24 ll l = Default::read<ll>(), r = Default::read<ll>();
25 if(r <= PRE){
26 for(int i = l; i <= r; ++i){
27 printf("%c", mu[i] == 1 ? '+' : (mu[i] == -1 ? '-' : '0'));
28 }
29 printf("\n");
30 continue;
31 }
32 int siz = r - l + 1;
33 ll value[1100000];
34 for(int i = 1; i <= siz; ++i)value[i] = (ll)i + l - 1;
35 int mu_r[1100000];
36 memset(mu_r, 0x3f, sizeof(mu_r));
37 for(auto p : prime){
38 ll times = l / p;
39 ll beg = p * times;
40 while(beg < l)beg += p;
41 while(beg <= r){
42 value[RPOS] /= p;
43 if(value[RPOS] % p == 0)mu_r[RPOS] = 0;
44 mu_r[RPOS] = mu_r[RPOS] > 1 ? -1 : -mu_r[RPOS];
45 beg += p;
46 }
47 }
48 for(int i = 1; i <= siz; ++i){
49 if(mu_r[i] == 0 || value[i] == 1)continue;
50 if(Default::MillerRabin(value[i], true))mu_r[i] = mu_r[i] > 1 ? -1 : -mu_r[i];
51 else if(value[i] != 1 && (ll)sqrt(value[i]) * (ll)sqrt(value[i]) == value[i])mu_r[i] = 0;
52 else if(mu_r[i] > 1)mu_r[i] = 1;
53 }
54 for(int i = 1; i <= siz; ++i)printf("%c", mu_r[i] == 1 ? '+' : (mu_r[i] == -1 ? '-' : mu_r[i] == 0 ? '0' : '?'));
55 printf("\n");
56 }
57 }
58}
观察文件名 g
显然是要求区间内的数是否为原根。对于第一个点模数全为
对于其所有质因数
对于第二个点多了一个
对于原根
可以考虑把其分解质因数,标记所有其质因数的区间内的倍数,也就是筛一下,最终所有没有标记的数可以表示为
然后对于最后一个点,和之前的思路一样,显然模数是质数,把模数枚举一下,然后选二十个左右的数据,随便选一个质因子验证一下,很快就能跑出来模数为
xxxxxxxxxx
781namespace Case_14_15_16{
2
3 vector < ll > prime;
4 bool vis[PRE + 100];
5 void Pretreat(void){
6 vis[1] = true;
7 for(int i = 2; i <= PRE; ++i){
8 if(!vis[i])prime.push_back(i), vis[i] = true;
9 for(auto p : prime){
10 if(p * i > PRE)break;
11 vis[p * i] = true;
12 if(i % p == 0)break;
13 }
14 }
15 }
16 vector < ll > Resolve(ll x){
17
18
19 Pretreat();
20 //PRETREAT
21 vector < ll > ret;
22 for(auto p : prime){
23 if(p * p > x)break;
24 if(x % p == 0)ret.push_back(p);
25 while(x % p == 0)x /= p;
26 }
27 if(x != 1)ret.push_back(x);
28 return ret;
29 }
30 map < ll, ll > mp;
31 ll FindMinG(ll x){
32 if(mp.find(x) != mp.end())return mp[x];
33 vector < ll > fact = Resolve(x - 1);
34 for(ll i = 2; i <= (ll)pow(x, 0.25); ++i){
35 bool flag(true);
36 for(auto p : fact){
37 if(Default::qpow(i, (x - 1) / p, x) == 1){flag = false; break;}
38 }
39 if(flag){
40 mp.insert({x, i});
41 return i;
42 }
43 }
44 return -1;
45 }
46 void Make(void){
47 int N = Default::read();
48 for(int i = 1; i <= N; ++i){
49 ll l = Default::read<ll>(), r = Default::read<ll>();
50 ll MOD = l != 233333333ll ? Default::read<ll>() : 1515343657ll;
51 if(MOD == 998244353ll || MOD == 1515343657ll){
52 vector < ll > frac = Resolve(MOD - 1);
53 for(ll x = l; x <= r; ++x){
54 bool flag(true);
55 for(auto p : frac)
56 if(Default::qpow(x, (MOD - 1) / p, MOD) == 1){printf("."); flag = false; break;}
57 if(flag)printf("g");
58 }
59 printf("\n");
60 continue;
61 }
62 vector < ll > frac = Resolve(MOD - 1);
63 ll G = FindMinG(MOD);//fprintf(stderr, "G: %lld\n", G);
64
65 bool mark[CMOD + 100];
66 for(auto p : frac)
67 for(ll j = 1; j * p <= CMOD; ++j)
68 mark[j * p] = true;
69 int logg[CMOD + 100];
70 memset(logg, 0, sizeof(logg));
71 for(ll cur(1), base(0); base <= CMOD; ++base, cur = cur * G % CMOD)
72 logg[cur] = base;
73 for(ll x = l; x <= r; ++x)
74 printf("%c", mark[logg[x]] ? '.' : 'g');
75 printf("\n");
76 }
77 }
78}
xxxxxxxxxx
3091
2
3
4
5
6
7
8
9using namespace std;
10
11mt19937 rnd(random_device{}());
12int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
13
14typedef unsigned int uint;
15typedef unsigned long long unll;
16typedef long long ll;
17typedef long double ld;
18
19namespace Default{
20 mt19937 rnd(random_device{}());
21 int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
22 template<typename T = int>
23 inline T read(void){
24 T ret(0);
25 short flag(1);
26 char c = getchar();
27 while(c != '-' && !isdigit(c))c = getchar();
28 if(c == '-')flag = -1, c = getchar();
29 while(isdigit(c)){
30 ret *= 10;
31 ret += int(c - '0');
32 c = getchar();
33 }
34 ret *= flag;
35 return ret;
36 }
37 ll readBignum(ll MOD){
38 ll ret(0);
39 char c = getchar();
40 while(!isdigit(c))c = getchar();
41 while(isdigit(c)){
42 ret = (ret * 10 + int(c - '0')) % MOD;
43 c = getchar();
44 }
45 return ret;
46 }
47 ll readBignum(ll MOD, string num){
48 ll ret(0);
49 for(auto c : num){
50 if(!isdigit(c))continue;
51 ret = (ret * 10 + int(c - '0')) % MOD;
52 }
53 return ret;
54 }
55 ll qmul(ll x, ll y, ll MOD){
56 return (__int128_t)x * y % MOD;
57 // ll quot = (ld)x / MOD * y;
58 // ll ret = (unll)x * y - (unll)quot * MOD;
59 // return (ret + MOD) % MOD;
60 }
61 ll qpow(ll a, ll b, ll MOD){
62 ll ret(1), mul(a);
63 while(b){
64 if(b & 1)ret = qmul(ret, mul, MOD);
65 b >>= 1;
66 mul = qmul(mul, mul, MOD);
67 }
68 return ret;
69 }
70 bool MillerRabin(ll n, bool special = false){
71 int prime[20] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
72 if(n % 2 == 0 || n <= 2)return n == 2;
73 ll power(n - 1); int cnt(0);
74 while(power % 2 == 0)power /= 2, ++cnt;
75 int times = special ? 1 : 12;
76 while(times--){
77 if(n == prime[times + 1])return true;
78 ll base = prime[times + 1], res = qpow(base, power, n);
79 ll nxt;
80 // if(res == n - 1 || res == 1)continue;
81 for(int i = 1; i <= cnt; ++i){
82 nxt = qmul(res, res, n);
83 if(nxt == 1 && res != 1 && res != n - 1)return false;
84 res = nxt;
85 }
86 if(nxt != 1)return false;
87 }
88 return true;
89 }
90}
91
92namespace Case_1_2_3{
93 void Make(ll MOD = 998244353){
94 int N = Default::read();
95 for(int i = 1; i <= N; ++i){
96 ll x = Default::readBignum(MOD - 1);
97 printf("%lld\n", Default::qpow(19, x, MOD));
98 }
99 }
100}
101namespace Case_4{
102 ll FindMod(void){
103 string val_s("627811703016764290815178977207148434322");
104 ll std_res = 642666;
105 for(ll i = 1145099 + 1; i <= LLONG_MAX; ++i){
106 if(i % 2 == 0 || !Default::MillerRabin(i))continue;
107 ll val = Default::readBignum(i - 1, val_s);
108 ll res = Default::qpow(19, val, i);
109 if(res == std_res)return i;
110 }
111 }
112 void Make(void){
113 Case_1_2_3::Make(1145141ll);
114 }
115}
116namespace Case_5{
117 void Make(void){
118 Case_1_2_3::Make(5211600617818708273ll);
119 }
120}
121namespace Case_6_7{
122 const int MOD(998244353);
123 int ans[11000000];
124 int beg(-1), siz(-1);
125 void FindCirc(void){
126 map < int, int > mp;
127 int base(1);
128 mp.insert({ans[0] = base, 0});
129 for(int i = 1; true; ++i){
130 if(mp.find(base = signed((unsigned)base * (unsigned)19) % MOD) != mp.end()){beg = mp[base], siz = i - mp[base]; return;}
131 else mp.insert({ans[i] = base, i});
132 }
133 }
134 void Make(void){
135 FindCirc();
136 int N = Default::read();
137 for(int i = 1; i <= N; ++i){
138 ll x = Default::read<ll>();
139 if(x < beg)printf("%d\n", ans[x]);
140 else printf("%d\n", ans[(x - beg) % siz + beg]);
141 }
142 }
143}
144namespace Case_8_9_10{
145 void Make(void){
146 int N = Default::read();
147 for(int i = 1; i <= N; ++i){
148 ll l = Default::read<ll>(), r = Default::read<ll>();
149 for(ll x = l; x <= r; ++x){
150 printf("%c", Default::MillerRabin(x) ? 'p' : '.');
151 }
152 printf("\n");
153 }
154 }
155}
156namespace Case_11_12_13{
157
158
159 void Make(void){
160 vector < int > prime;
161 bool vis[PRE + 10];
162 int mu[PRE + 10];
163 vis[1] = true, mu[1] = 1;
164 for(int i = 2; i <= PRE; ++i){
165 if(!vis[i]){
166 vis[i] = true;
167 mu[i] = -1;
168 prime.push_back(i);
169 }
170 for(auto p : prime){
171 if(p * i > PRE)break;
172 vis[p * i] = true;
173 mu[p * i] = i % p == 0 ? 0 : -mu[i];
174 if(i % p == 0)break;
175 }
176 }
177 int N = Default::read();
178 while(N--){
179 ll l = Default::read<ll>(), r = Default::read<ll>();
180 if(r <= PRE){
181 for(int i = l; i <= r; ++i){
182 printf("%c", mu[i] == 1 ? '+' : (mu[i] == -1 ? '-' : '0'));
183 }
184 printf("\n");
185 continue;
186 }
187 int siz = r - l + 1;
188 ll value[1100000];
189 for(int i = 1; i <= siz; ++i)value[i] = (ll)i + l - 1;
190 int mu_r[1100000];
191 memset(mu_r, 0x3f, sizeof(mu_r));
192 for(auto p : prime){
193 ll times = l / p;
194 ll beg = p * times;
195 while(beg < l)beg += p;
196 while(beg <= r){
197 value[RPOS] /= p;
198 if(value[RPOS] % p == 0)mu_r[RPOS] = 0;
199 mu_r[RPOS] = mu_r[RPOS] > 1 ? -1 : -mu_r[RPOS];
200 beg += p;
201 }
202 }
203 for(int i = 1; i <= siz; ++i){
204 if(mu_r[i] == 0 || value[i] == 1)continue;
205 if(Default::MillerRabin(value[i], true))mu_r[i] = mu_r[i] > 1 ? -1 : -mu_r[i];
206 else if(value[i] != 1 && (ll)sqrt(value[i]) * (ll)sqrt(value[i]) == value[i])mu_r[i] = 0;
207 else if(mu_r[i] > 1)mu_r[i] = 1;
208 }
209 for(int i = 1; i <= siz; ++i)printf("%c", mu_r[i] == 1 ? '+' : (mu_r[i] == -1 ? '-' : mu_r[i] == 0 ? '0' : '?'));
210 printf("\n");
211 }
212 }
213
214
215}
216namespace Case_14_15_16{
217
218 vector < ll > prime;
219 bool vis[PRE + 100];
220 void Pretreat(void){
221 vis[1] = true;
222 for(int i = 2; i <= PRE; ++i){
223 if(!vis[i])prime.push_back(i), vis[i] = true;
224 for(auto p : prime){
225 if(p * i > PRE)break;
226 vis[p * i] = true;
227 if(i % p == 0)break;
228 }
229 }
230 }
231 vector < ll > Resolve(ll x){
232
233
234 Pretreat();
235 //PRETREAT
236 vector < ll > ret;
237 for(auto p : prime){
238 if(p * p > x)break;
239 if(x % p == 0)ret.push_back(p);
240 while(x % p == 0)x /= p;
241 }
242 if(x != 1)ret.push_back(x);
243 return ret;
244 }
245 map < ll, ll > mp;
246 ll FindMinG(ll x){
247 if(mp.find(x) != mp.end())return mp[x];
248 vector < ll > fact = Resolve(x - 1);
249 for(ll i = 2; i <= (ll)pow(x, 0.25); ++i){
250 bool flag(true);
251 for(auto p : fact){
252 if(Default::qpow(i, (x - 1) / p, x) == 1){flag = false; break;}
253 }
254 if(flag){
255 mp.insert({x, i});
256 return i;
257 }
258 }
259 return -1;
260 }
261 void Make(void){
262 int N = Default::read();
263 for(int i = 1; i <= N; ++i){
264 ll l = Default::read<ll>(), r = Default::read<ll>();
265 ll MOD = l != 233333333ll ? Default::read<ll>() : 1515343657ll;
266 if(MOD == 998244353ll || MOD == 1515343657ll){
267 vector < ll > frac = Resolve(MOD - 1);
268 for(ll x = l; x <= r; ++x){
269 bool flag(true);
270 for(auto p : frac)
271 if(Default::qpow(x, (MOD - 1) / p, MOD) == 1){printf("."); flag = false; break;}
272 if(flag)printf("g");
273 }
274 printf("\n");
275 continue;
276 }
277 vector < ll > frac = Resolve(MOD - 1);
278 ll G = FindMinG(MOD);//fprintf(stderr, "G: %lld\n", G);
279
280 bool mark[CMOD + 100];
281 for(auto p : frac)
282 for(ll j = 1; j * p <= CMOD; ++j)
283 mark[j * p] = true;
284 int logg[CMOD + 100];
285 memset(logg, 0, sizeof(logg));
286 for(ll cur(1), base(0); base <= CMOD; ++base, cur = cur * G % CMOD)
287 logg[cur] = base;
288 for(ll x = l; x <= r; ++x)
289 printf("%c", mark[logg[x]] ? '.' : 'g');
290 printf("\n");
291 }
292 }
293}
294
295int main(){
296 // freopen("in.txt", "r", stdin);
297 // freopen("out.txt", "w", stdout);
298 string filename; cin >> filename;
299 if(!filename.compare("1_998244353"))Case_1_2_3::Make();
300 if(!filename.compare("1?"))Case_4::Make();
301 if(!filename.compare("1?+"))Case_5::Make();
302 if(!filename.compare("1wa_998244353"))Case_6_7::Make();
303 if(!filename.compare("2p"))Case_8_9_10::Make();
304 if(!filename.compare("2u"))Case_11_12_13::Make();
305 if(!filename.compare("2g") || ! filename.compare("2g?"))Case_14_15_16::Make();
306
307 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
308 return 0;
309}
update-2022_09_20 初稿