Java教程
2021.1.21 模拟赛题解
本文主要是介绍2021.1.21 模拟赛题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
T1. star
给出 \(k,m\)，求方程 \(k^x=1\pmod{m}\) 的 \(x\) 的最小正整数解。
若无解，输出 No Solution。
多测，\(1 \leq T \leq 10^3,2 \leq m,k\leq 10^9\)。
sol
无解：\(\gcd(k,m) \ne 1\)。
套个 BSGS \(\mathcal O(\sqrt{n})\) 求即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp(a, b) make_pair(a, b)
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
void write(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template<typename T>
T exgcd(T a, T b, T &x, T &y)
{
if(!b) return x = 1, y = 0, a;
int d = exgcd(b, a % b, y, x);
return y -= a / b * x, d;
}
int gcd(int a, int b)
{
if(!b) return a;
return gcd(b, a % b);
}
inline int BSGS(int a, int b, int m)
{
static unordered_map<int, int> buk;
buk.clear();
int S = sqrt(m - 1) + 1;
int A = 1, f = -1;
for(int i = 0; i < S; ++i)
{
buk[b * A % m] = i;
A = A * a % m;
}
int C = 1;
for(int i = 1; i <= S; ++i)
{
C = C * A % m;
auto it = buk.find(C);
if(it != buk.end())
return i * S - it->second;
}
return -1;
}
int a, b, m;
signed main()
{
int t = read();
while(t--)
{
m = read(), a = read();
a %= m;
if(__gcd(a, m) != 1 || a == 0)
{
puts("No Solution");
continue;
}
int ans = BSGS(a, 1, m);
write(ans), putchar('\n');
}
return 0;
}
T2. 信号
给出 \(S,p,m,q,n\)，求方程 \(p+mx \equiv q+nx \pmod{S}\) 的最小 \(x\) 的正整数解。
\(1 \leq p,q,m,n,S < 2^{31}\)。
sol
套个 exgcd 即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
void write(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int s, p, m, q, n, x, y;
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int g = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return g;
}
signed main()
{
s = read(), p = read(), m = read(), q = read(), n = read();
int a = ((n - m) % s + s) % s, c = ((p - q) % s + s) % s;
if (c % gcd(a, s) != 0)
{
puts("Cannot Get The Secret!");
return 0;
}
int g = exgcd(a, s, x, y);
x *= (c / gcd(a, s));
int kkk = s / g;
x = (x % kkk + kkk) % kkk;
if (x == 0)
x += kkk;
write(x);
return 0;
}
T3. Modulus
给你 \(n,m\)，表示有 \(m\) 个询问，每组询问形如 l,r，表示求 \(\forall l \leq j \leq r,\max(n \bmod j)\)。
\(1 \leq n \leq 10^{10},1 \leq m \leq 10^5\)。
sol
显然的数论分块。
但显然不能边数论分块边回答询问。
考虑将数论分块预处理好。
根据 \(n \bmod j=n-\lfloor\frac{n}{j}\rfloor \cdot j\)。
可转换为求 \(\lfloor\frac{n}{j}\rfloor \cdot j\) 的最小值。
根据 \(\lfloor\frac{n}{j}\rfloor\) 的值相同的一个块内，最小值显然处于左端点。
所以上述做法正确性显然。
细节：
\(l\) 如果不处于它块的左端点，那么它这个块就需要特判一下。
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, sq;
const int _ = 4e5 + 7;
int tot, p[_], q[_];
int a[_][22];
int lg[_];
void update()
{
for (int j = 1; (1 << j) <= tot; j++)
{
for (int i = 1; i + (1 << j) - 1 <= tot; i++)
{
a[i][j] = min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r)
{
if (l > r)
return 0;
int t = lg[r - l + 1] - 1;
return min(a[l][t], a[r - (1 << t) + 1][t]);
}
int erfenl(int x)
{
int l = 1, r = tot, mid;
while(l <= r)
{
mid = (l + r) >> 1;
// cout << mid << "\n";
if(x >= p[mid] && x <= q[mid])
{
if(x > p[mid]) return mid + 1;
return mid;
}
else if(x < p[mid])
{
r = mid - 1;
}
else if(x > q[mid])
{
l = mid + 1;
}
}
}
int erfenr(int x)
{
int l = 1, r = tot, mid, ans = 0;
while(l <= r)
{
mid = (l + r) >> 1;
if(x >= p[mid] && x <= q[mid])
{
return mid;
}
else if(x < p[mid])
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
}
signed main()
{
// freopen("ex.in", "r", stdin);
// freopen("2.out", "w", stdout);
for(int i = 0; i < _; ++i)
for(int j = 0; j < 21; ++j) a[i][j] = 1e10 + 7;
n = read(), m = read();
sq = sqrt(n);
for(int i = 1, j; i <= n; i = j + 1)
{
j = n / (n / i);
p[++tot] = i, q[tot] = j;
a[tot][0] = (n / i) * p[tot];
}
for (int i = 1; i <= tot; ++i)
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
update();
while(m--)
{
int l = read(), r = read();
if(l > r) swap(l, r);
int L = erfenl(l), R = erfenr(r);
if(L > R)
{
write(n - (n / l) * l);
putchar('\n');
continue;
}
write(n - query(L, R));
putchar('\n');
}
return 0;
}
T4. 教主的魔法
区间加，区间查询 \(\ge c\) 的数的个数。
sol
分块。
区间加用 lazytag 维护。
查询二分预处理即可。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 1e6 + 7;
int n, q;
int a[_], l[_], r[_], d[_], bel[_], lz[_];
int blo, tot;
void cg(int x)
{
for(int i = l[bel[x]]; i <= r[bel[x]]; ++i) d[i] = a[i];
sort(d + l[bel[x]], d + r[bel[x]] + 1);
}
void change(int x, int y, int k)
{
if(bel[x] == bel[y])
{
for(int i = x; i <= y; ++i) a[i] += k;
cg(x);
}
else
{
for(int i = x; i <= r[bel[x]]; ++i) a[i] += k;
cg(x);
for(int i = l[bel[y]]; i <= y; ++i) a[i] += k;
cg(y);
for(int i = bel[x] + 1; i <= bel[y] - 1; ++i) lz[i] += k;
}
}
int query(int x, int y, int k)
{
int ans = 0;
if(bel[x] == bel[y])
{
for(int i = x; i <= y; ++i)
if(lz[bel[x]] + a[i] >= k) ans++;
return ans;
}
else
{
for(int i = x; i <= r[bel[x]]; ++i)
if(lz[bel[x]] + a[i] >= k) ans++;
for(int i = l[bel[y]]; i <= y; ++i)
if(lz[bel[y]] + a[i] >= k) ans++;
for(int i = bel[x] + 1; i <= bel[y] - 1; ++i)
ans += r[i] - (lower_bound(d + l[i], d + r[i] + 1, k - lz[i]) - d) + 1;
return ans;
}
}
signed main()
{
n = read(), q = read();
for(int i = 1; i <= n; ++i) a[i] = read();
blo = sqrt(n), tot = n / blo;
if(n % blo) tot++;
for(int i = 1; i <= n; ++i)
bel[i] = (i - 1) / blo + 1, d[i] = a[i];
for(int i = 1; i <= tot; ++i)
l[i] = (i - 1) * blo + 1, r[i] = i * blo;
r[tot] = n;
for(int i = 1; i <= tot; ++i)
sort(d + l[i], d + r[i] + 1);
while(q--)
{
char s[10];
scanf("%s", s);
int x = read(), y = read(), c = read();
if(x > y) swap(x, y);
if(s[0] == 'M')
{
change(x, y, c);
}
else
{
write(query(x, y, c));
putchar('\n');
}
}
return 0;
}
这篇关于2021.1.21 模拟赛题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
线下车企门店如何实现线上线下融合？12-23
-
鸿蒙Next ArkTS编程规范总结12-23
-
物流团队冬至高效运转，哪款办公软件可助力风险评估？12-23
-
优化库存，提升效率：医药企业如何借助看板软件实现仓库智能化12-23
-
项目管理零负担！轻量化看板工具如何助力团队协作12-23
-
电商活动复盘，为何是团队成长的核心环节？12-23
-
鸿蒙Next ArkTS高性能编程实战12-23
-
数据驱动：电商复盘从基础到进阶！12-23
-
从数据到客户：跨境电商如何通过销售跟踪工具提升营销精准度？12-23
-
汽车4S店运营效率提升的核心工具12-23
-
ERP 系统开发案例：用 PERT 图打造高效项目管理12-23
-
初创团队必备！全面解析支持甘特图的项目管理工具与功能特点12-23
-
任务进度跟踪不再难！可视化项目协作工具精选12-23
-
看板工具为汽车销售门店协作赋能：关键方法12-23
-
0.96寸OLED显示屏详解12-23
栏目导航
