2020 Petrozavodsk Winter Camp Day 5 A | Nanako

2020 Petrozavodsk Winter Camp Day 5 A

Problem A. Bags of Candies

Statement

把 $A = \{1,2,\dots,n\}$ 分成尽可能多对,使得每一对的两个数都不互质,问 $n$ 减去配对次数的值。有 $z$ 组测试数据。

$1 \leq z \leq 5$

$2 \leq n \leq 10^{11}$

Solution

半场的时候动这个题的队伍只有个位数。可能大家都觉得有别的题可做,不像我这么菜别的都不会就来瞎猜结论了啊。于是结论就是,将 $1$ 和大于 $\lfloor \frac n2 \rfloor$ 的质数从 $A$ 里删掉,剩下的集合 $A’$ 一定是可以匹配满的,所以配对次数就是 $\frac {|A’|}2$。

赛中是瞎猜的,这里给一个简单证明。

将 $A’$ 的所有元素按最大质因子 $d$ 分组,那么每组都可以表示成 $A_d = \{d,2d,\dots,\lfloor \frac nd \rfloor d\}$ 的形式(注意并不一定 $|A_d|=\lfloor \frac nd \rfloor$,比如 $77 \notin A_7$),显然组内的数都是不互质的。

如果 $|A_d|$ 是偶数,直接令组内的数任意两两配对;如果 $|A_d|$ 是奇数,则除了 $2d$ 以外任意两两配对。所有组都作完以上匹配之后,剩下的数都是 $2$ 的倍数,所以也都不互质,也可以任意两两配对。注意到对于任意 $d$ 有 $|A_d| \geq 2$ 即不存在 $|A_d| = 1$,所以最后剩下的数显然至多只有一个。

至此,剩下的任务就是筛 $10^{11}$ 以内的质数个数。这东西听上去很不可做,又或者是某种奥妙重重的高级筛法,但 clp012345 说有一种叫作 Meissel-Lehmer 的神棍算法可以 $O(n^\frac 23)$ 求这个东西,于是我临时找了个板子复制粘贴交了两发过了(?)。赛后看官方题解居然是分段打表,太暴力了……

关于这个算法的更多内容可以看上面的链接。

Code

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
152
153
154
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main0 ();
int main () {
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
clock_t start, end;
// start = clock();
main0();
// end = clock();
// cout << (end - start) << endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}

const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);

const int N = 5e6 + 2;//通过知道前面的n^1/3的=质数可以推断后面n^2/3的质数所以可以适当减小
bool np[N];
int prime[N], pi[N];
int getprime()
{
int cnt = 0;
np[0] = np[1] = true;
pi[0] = pi[1] = 0;
for(int i = 2; i < N; ++i)
{
if(!np[i]) prime[++cnt] = i;
pi[i] = cnt;
for(int j = 1; j <= cnt && i * prime[j] < N; ++j)
{
np[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
return cnt;
}
const int M = 7;//为了减小内存可以不过是质数
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;//为了减小内存可以不过要按质数减小如去掉17
int phi[PM + 1][M + 1], sz[M + 1];
void init()
{
getprime();
sz[0] = 1;
for(int i = 0; i <= PM; ++i) phi[i][0] = i;
for(int i = 1; i <= M; ++i)
{
sz[i] = prime[i] * sz[i - 1];
for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
}
}
int sqrt2(ll x)
{
ll r = (ll)sqrt(x - 0.1);
while(r * r <= x) ++r;
return int(r - 1);
}
int sqrt3(ll x)
{
ll r = (ll)cbrt(x - 0.1);
while(r * r * r <= x) ++r;
return int(r - 1);
}
ll getphi(ll x, int s)
{
if(s == 0) return x;
if(s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
if(x <= prime[s]*prime[s]) return pi[x] - s + 1;
if(x <= prime[s]*prime[s]*prime[s] && x < N)
{
int s2x = pi[sqrt2(x)];
ll ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
return ans;
}
return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
ll getpi(ll x)
{
if(x < N) return pi[x];
ll ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
return ans;
}
ll lehmer_pi(ll x)
{
if(x < N) return pi[x];
int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
int b = (int)lehmer_pi(sqrt2(x));
int c = (int)lehmer_pi(sqrt3(x));
ll sum = getphi(x, a) +(ll)(b + a - 2) * (b - a + 1) / 2;
for (int i = a + 1; i <= b; i++)
{
ll w = x / prime[i];
sum -= lehmer_pi(w);
if (i > c) continue;
ll lim = lehmer_pi(sqrt2(w));
for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
}
return sum;
}

int main0 () {
init();
MULTI {
ll n;
cin >> n;
//cout << lehmer_pi(n) << ' ' << lehmer_pi(n / 2) << endl;
ll k = lehmer_pi(n) - lehmer_pi(n / 2) + 1;
cout << n - (n - k) / 2 << endl;
}
}

欢迎关注我的其它发布渠道