比赛链接
收获
B Basic Gcd Problem
答案其实就是 $c^{p(n)}$，其中 $p(n)$ 表示 $n$ 的质因数个数（要重复统计，例如 $p(12)=p(2\times2\times3)=3$）。
$p(n)$ 自然可以先线性筛得到素数，再分解 $n$ 计算；但是还可以更快的直接改一改线性筛就可以了。详见代码。
B.cpp >folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 1000005;
bool notP[N];
int pList[N], pID, pf[N];
void Euler(int n){
notP[0] = notP[1] = 1;
for(int i = 1; i <= n; i++){
if(!notP[i]) pList[++pID] = i, pf[i] = 1;
for(int j = 1; j <= pID; j++){
if(1ll * i * pList[j] > n) break;
notP[i * pList[j]] = 1;
pf[i * pList[j]] = pf[i] + 1;
if(i % pList[j] == 0) break;
}
}
}
const LL MOD = 1e9+7;
inline LL fpow(LL bs, LL idx){
LL res = 1;
bs %= MOD;
while(idx){
if(idx & 1) (res *= bs) %= MOD;
(bs *= bs) %= MOD;
idx >>= 1;
}
return res;
}
int T;
LL n, c;
int main(){
Euler(1000000);
for(read(T); T; T--){
read(n, c);
printf("%lld\n", fpow(c, pf[n]));
}
return 0;
}
|
F Finding the Order
假设 $a<b$（否则交换一下并打个标记），那么 $AC,AD$ 一定形如下图（$D$ 在另一侧是对称的，只用考虑一侧）：
找到 $A$ 关于 $D$ 的对称位置，那么如上图，我们得到了三个区域：
- 如果 $d\leqslant b$，$B$ 在第二个区域
- 否则，$d>b$，$B$ 可能在第一个或者第三个区域
- 若 $c>d$，$B$ 在第三个区域
- 否则，$B$ 在第一个区域
没错，我又做复杂了，根据两边之和大于第三边，判断一下 $AD+BC>AC+BD$ 就好了。呜呜呜～
F.cpp >folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, a, b, c, d;
int main(){
for(read(T); T; T--){
read(a, b, c, d);
bool sw = false, ABCD = true;
if(a > b) sw = true, swap(a, b), swap(c, d);
if(d <= b) ABCD = true;
else{
if(d > c) ABCD = false;
else ABCD = true;
}
ABCD ^= sw;
if(ABCD) puts("AB//CD");
else puts("AB//DC");
}
return 0;
}
|
H Harder Gcd Problem
题目要求即将 $\{1,2,\cdots,n\}$ 两两配成不互质的数对，问最多配成多少对并给出一种方案。
先说一下我的做法：
将所有数质因数分解，$a={p_1}^{k_1}{p_2}^{k_2}\cdots{p_r}^{k_r}$，这道题中 $k_1,k_2,\cdots,k_r$ 并不是重点，所以可以置 $a:=a’=p_1p_2\cdots p_r$，并记录下它的不同质因数个数 $r$。容易想到的是，一个数不同的质因数越多，它就越可能去跟别人匹配，所以我们把 $\{1,2,\cdots,n\}$ 以 $r$ 为第一关键字，以 $a’$ 为第二关键字排序后，从前往后依次考虑还没有匹配的数，用它后面第一个能与它匹配的数去匹配。
实现上，注意 $2e5$ 范围内的数最多有 $6$ 个不同的质因数，所以可以对每个质数开一个队列，存储哪些数有这个质因子（这些队列的大小总和不超过 $6\times2e5$），注意存储的顺序是按照排序后的顺序。那么枚举到一个待匹配的数，就找它的质因子的那些队列（最多 $6$ 个队列），选排序后位置最靠前的和它匹配即可。
然后是另外的一个构造做法：
首先，大于 $\frac{n}{2}$ 的质数是不可能匹配的，然后再把 $1$ 去掉，剩下的数两两匹配是答案的理论上界，而事实上这个上界是可以构造出来的。
从大到小考虑小于 $\frac{n}{2}$ 的那些质数，如果它们及其倍数 $p,2p,\cdots,kp$ 是偶数个就全部匹配（当然去除已匹配的），否则单出一个 $2p$；这样匹配完之后剩下的数都是 $2$ 的倍数，随便匹配即可。
H.cpp >folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
bool notP[N];
int pList[N], pID;
void Euler(int n){
notP[0] = notP[1] = 1;
for(int i = 1; i <= n; i++){
if(!notP[i]) pList[++pID] = i;
for(int j = 1; j <= pID; j++){
if(1ll * i * pList[j] > n) break;
notP[i * pList[j]] = 1;
if(i % pList[j] == 0) break;
}
}
}
struct Node{
int num, cnt;
int val;
bool operator < (const Node &A) const{
return cnt == A.cnt ? val < A.val : cnt < A.cnt;
}
}a[N];
vector<int> fac[N];
inline void preprocess(){
Euler(200000);
for(int i = 2; i <= 200000; i++){
int n = i;
for(int j = 1; pList[j] * pList[j] <= n; j++){
if(n % pList[j] == 0) fac[i].pb(pList[j]);
while(n % pList[j] == 0) n /= pList[j];
}
if(n > 1) fac[i].pb(n);
}
}
int T, n;
int main(){
preprocess();
for(read(T); T; T--){
read(n);
vector< queue<int> > b(n+5, queue<int>());
vector<bool> tag(n+5);
vector<pii> ans;
vi pos(n+5);
for(int i = 1; i <= n; i++){
a[i].num = i, a[i].cnt = fac[i].size();
a[i].val = 1; for(auto &factor : fac[i]) a[i].val *= factor;
}
sort(a+1, a+n+1);
for(int i = 1; i <= n; i++) pos[a[i].num] = i;
for(int i = 1; i <= n; i++)
for(auto &factor : fac[a[i].num])
b[factor].push(a[i].num);
for(int i = 1; i <= n; i++){
if(tag[a[i].num]) continue;
tag[a[i].num] = true;
bool ok = false;
int mnpos = 1e9, mark = 0;
for(auto &factor : fac[a[i].num]){
while(!b[factor].empty() && tag[b[factor].front()])
b[factor].pop();
if(b[factor].empty()) continue;
if(mnpos > pos[b[factor].front()]){
mnpos = pos[b[factor].front()];
mark = factor;
}
}
if(mark == 0) continue;
tag[b[mark].front()] = true;
ans.pb(mp(a[i].num, b[mark].front()));
b[mark].pop();
}
printf("%d\n", (int)ans.size());
for(auto &res : ans)
printf("%d %d\n", res.first, res.second);
}
return 0;
}
|
构造做法（好写很多）：
H2.cpp >folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
bool notP[N];
int pList[N], pID;
void Euler(int n){
notP[0] = notP[1] = 1;
for(int i = 1; i <= n; i++){
if(!notP[i]) pList[++pID] = i;
for(int j = 1; j <= pID; j++){
if(1ll * i * pList[j] > n) break;
notP[i * pList[j]] = 1;
if(i % pList[j] == 0) break;
}
}
}
int main(){
Euler(200000);
int T, n; for(read(T); T; T--){
read(n);
vector<pii> ans;
vector<bool> tag(n+5);
vi rem;
int pt = 0;
for(pt = 1; pList[pt] * 2 <= n; pt++); pt--;
for(int i = pt; i >= 2; i--){
vi v;
for(int k = 1; k * pList[i] <= n; k++)
if(!tag[k*pList[i]] && k != 2)
v.pb(k);
for(int k = 0; k + 1 < v.size(); k += 2){
ans.pb(mp(v[k]*pList[i], v[k+1]*pList[i]));
tag[v[k]*pList[i]] = tag[v[k+1]*pList[i]] = true;
}
if(v.size() & 1){
ans.pb(mp(v.back()*pList[i], 2*pList[i]));
tag[v.back()*pList[i]] = tag[2*pList[i]] = true;
}
else rem.pb(2*pList[i]);
}
for(int i = 1; i * 2 <= n; i++)
if(!tag[i*2]) rem.pb(i*2);
sort(rem.begin(), rem.end());
rem.erase(unique(rem.begin(), rem.end()), rem.end());
for(int i = 0; i + 1 < rem.size(); i += 2)
ans.pb(mp(rem[i], rem[i+1]));
printf("%d\n", (int)ans.size());
for(auto &k : ans) printf("%d %d\n", k.first, k.second);
}
return 0;
}
|