比赛链接
收获
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$ 在另一侧是对称的,只用考虑一侧):
![F](/Users/jason/blog/source/_posts/2020牛客暑期多校训练营(第四场)/F.png)
找到 $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; }
|