CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Enju With math problem
见过几次的套路题了。题目给的范围内，素数出现的最大间隔有两百多个，所以暴力判断其中某一个一定是素数是不够的。这里我判断是否存在一个数是某两个素数乘积p*q的形式，并用前一百个素数带入p暴力检验，终于在最后一分钟 A 掉了这个题！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //??a?b????????,??????,????????
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //??a?b??????????????
ll mul(ll a, ll b) const { return add(a * b, M); }
ll inv(ll a) const { return pow(a, M - 2); } //??M???,??return pow(a, phi(M) - 1);
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
};
struct EulerSieve
{
vector<int> p, m; //????,?????,????,??????
EulerSieve(int N) : m(N, 0)
{
for (long long i = 2, k; i < N; ++i) //?i*p[j]?int
{
if (!m[i])
p.push_back(m[i] = i); //i???
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
if ((m[k] = p[j]) == m[i])
break;
}
}
} e(1e7 + 9);
struct PollardRho
{
bool isPrime(ll n, int S = 12) //MillerRabin????,S?????,??S??????,S=12???unsigned long long?????;n<2???
{
static ll d, u, t, p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (d = n - 1; !(d & 1);)
d >>= 1; //??0,1???!
Mod mo(n);
for (int i = 0; i < S; ++i)
{
if (!(n % p[i]))
return n == p[i];
for (t = mo.pow(p[i], u = d); t != n - 1 && t != 1 && u != n - 1;)
t = mo.mul(t, t), u <<= 1;
if (t != n - 1 && !(u & 1))
return 0;
}
return 1;
}
void fac(ll n, vector<ll> &factor)
{
if (n < 2)
return;
if (n < e.m.size())
return factor.push_back(e.m[n]), fac(n /= e.m[n], factor);
if (isPrime(n))
return factor.push_back(n);
Mod mo(n);
for (ll c = 1;; ++c)
for (ll i = 0, k = 1, x = rand() % (n - 1) + 1, y, p;;)
{
if (++i == k)
y = x, k <<= 1;
if (x = mo.add(mo.mul(x, x), c), p = __gcd(abs(x - y), n), p == n)
break;
if (p > 1)
return fac(p, factor), fac(n / p, factor);
}
}
};
int t, a[500], b[200] = {0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24, 70, 24, 72, 36, 40, 36, 60, 24, 78, 32, 54, 40, 82, 24, 64, 42, 56, 40, 88, 24, 72, 44, 60, 46, 72, 32, 96, 42, 60, 40};
PollardRho pr;
vector<ll> vec;
inline int fai(int n)
{
vec.clear();
pr.fac(n, vec);
sort(vec.begin(), vec.end());
int sz = unique(vec.begin(), vec.end()) - vec.begin();
int ret = n;
for (int i = 0; i < sz; i++)
{
n = n / vec[i] * (vec[i] - 1);
}
return n;
}
inline bool check()
{
for (int i = 1; i <= 100; i++)
if (a[i] != b[i])
return false;
return true;
}
bool ok(int pos)
{
for (int j = 1; j <= 100; j++)
if (fai(pos + j - 1) != a[j])
return 0;
return 1;
}
int main(void)
{
scanf("%d", &t);
//freopen("qwr","w",stdout);
while (t--)
{
for (int i = 1; i <= 100; i++)
scanf("%d", &a[i]);
if (check())
{
printf("YES\n1\n");
continue;
}
bool ct2 = 0;
int pos;
for (int i = 1; i <= 100; i++)
{
if (ok(pos = a[i] - i + 2))
{
ct2 = 1;
break;
}
for (int j = 0; e.p[j] < 100; ++j)
if (a[i] % (e.p[j] - 1) == 0)
{
int q = a[i] / (e.p[j] - 1) + 1;
int p = e.p[j];
pos = p * q - i + 1;
if (ok(pos))
{
ct2 = 1;
break;
}
}
if (ct2)
break;
}
if (ct2)
{
printf("YES\n%d\n", pos);
}
else
puts("NO");
}
}
Fire-Fighting Hero
Dijkstra 跑一下即可，多起点连到一个虚拟节点，边长为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9 + 7;
struct Graph
{
struct Vertex
{
vector<int> o;
};
struct Edge
{
int first, second;
ll len; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct Dijkstra : Graph
{
vector<ll> d;
Dijkstra(int n) : Graph(n) {}
ll ask(int s)
{
d.assign(v.size(), INF);
priority_queue<pair<ll, int>> q;
ll r = 0;
for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
r = dis;
for (int i = 0, k, to; i != v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len;
q.push(make_pair(-d[to], to));
}
}
return r;
}
};
int main()
{
int t, v, e, s, k, c;
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d%d%d", &v, &e, &s, &k, &c);
Dijkstra g(v + 1);
for (int i = 0, t; i < k; ++i)
scanf("%d", &t), g.add({0, t, 0});
for (int i = 0, x, y, z; i < e; ++i)
{
scanf("%d%d%d", &x, &y, &z);
g.add({x, y, z});
g.add({y, x, z});
}
ll ans1 = g.ask(s), ans2 = g.ask(0);
printf("%d\n", ans1 <= ans2 * c ? ans1 : ans2);
}
}
Magic Master
暴力模拟即可，不知道为什么通过率这么低。也许是因为题面太长了？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int t, n, m, q;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 0, k; i < q; ++i)
{
scanf("%d", &k);
int hand = 0, desk = n;
while (k > 1)
{
++hand, --desk, --k;
k -= m;
while (k < 1)
k += desk;
}
printf("%d\n", hand + 1);
}
}
}
Pangu Separates Heaven and Earth
诚意很低的签到题，超长题面加超水签到题目？
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n;
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
puts(n == 1 ? "18000" : "0");
}
}
The Nth Item
标解要用到二次剩余，这里我按照$2^{20}$进制对矩阵乘法的结果预处理，使得每一个询问可以在三个矩阵乘法的时间内算出来，同时使用了小常数的做法，最终通过了这道题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define maxn (1 << 20)
using namespace std;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const
{
return a += b, a >= M ? a -= M : a; //??a?b????????,??????,????????
}
ll add(ll a, ll b) const
{
return qadd(a = (a + b) % M, M); //??a?b??????????????
}
ll mul(ll a, ll b) const
{
return add(a * b, M);
}
ll inv(ll a) const
{
return pow(a, M - 2); //??M???,??return pow(a, phi(M) - 1);
}
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
};
Mod m(mod);
struct mat
{
ll a, b, c, d;
mat operator*(const mat &q) const
{
return {(a * q.a + b * q.c) % mod,
(a * q.b + b * q.d) % mod,
(c * q.a + d * q.c) % mod,
(c * q.b + d * q.d) % mod};
}
};
mat a[3][maxn + 9] = {(mat){1, 0, 0, 1}, (mat){3, 2, 1, 0}};
ll q, n, ans, ansb;
int main(void)
{
scanf("%lld%lld", &q, &n);
for (int i = 2; i <= maxn; i++)
a[0][i] = a[0][i - 1] * a[0][1];
a[1][0] = (mat){1, 0, 0, 1};
a[1][1] = a[0][maxn];
for (int i = 2; i <= maxn; i++)
a[1][i] = a[1][i - 1] * a[1][1];
a[2][1] = a[1][maxn];
a[2][0] = (mat){1, 0, 0, 1};
for (int i = 2; i <= maxn; i++)
a[2][i] = a[2][i - 1] * a[2][1];
for (int i = 1; i <= q; i++)
{
n = n ^ (ans * ans);
// n=i;
mat tem = (mat){1, 0, 0, 1};
ll temn = n - 1;
if (temn)
{
tem = tem * a[0][temn - ((temn >> 20) << 20)], temn >>= 20;
if (temn)
{
tem = tem * a[1][temn - ((temn >> 20) << 20)], temn >>= 20;
if (temn)
tem = tem * a[2][temn - ((temn >> 20) << 20)], temn >>= 20;
}
}
ansb ^= ans = tem.a;
}
printf("%lld", ansb);
}