2020牛客暑期多校训练营（第四场）
B. Basic Gcd Problem
打表发现 F(n, c) = c ^ (n可以分解为多少个质因数)
用欧拉筛打出可以分解为多少个质因数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int pri[N], tot, cnt[N];
bool vis[N];
void init() {
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
vis[0] = vis[1] = 1;
tot = 0;
for(int i = 2; i < N; ++i) {
if(!vis[i]) {
pri[++tot] = i;
cnt[i]++;
}
for(int j = 1; j <= tot; ++j) {
if(i * pri[j] > N) break;
vis[i * pri[j]] = 1;
cnt[i * pri[j]] = cnt[i] + 1;
}
}
}
ll qpow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
int main() {
init();
int t, n, c;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &c);
cout<<qpow(1ll * c, 1ll * cnt[n]) % mod<<'\n';
}
return 0;
}
F. Finding the Order
题意：已知直线AB与直线CD平行，给出AC、AD、BC、BD，判断C、D的位置关系
思路1：四边形对角线之和大于两条对边和，比较AC + BD和AD + BC，大的是对角线
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int main() {
int t, ac, ad, bc, bd;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d%d", &ac, &ad, &bc, &bd);
if(ac + bd < ad + bc)
cout<<"AB//CD"<<'\n';
else
cout<<"AB//DC"<<'\n';
}
return 0;
}
思路2：先判断C、D和AB中垂线的关系，AC < BC时C在AB中垂线左，AC > BC时C在中垂线右，D点同理；若两点都在左侧，比较BC、BD；若两点都在右侧，比较AC、AD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int main() {
int t, ac, ad, bc, bd;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d%d", &ac, &ad, &bc, &bd);
int c = 0, d = 0; //左1 中0 右-1
if(ac < bc) c = 1;
else if(ac > bc) c = -1;
if(ad < bd) d = 1;
else if(ad > bd) d = -1;
if(c > d)
cout<<"AB//CD"<<'\n';
else if(c < d)
cout<<"AB//DC"<<'\n';
else {
if(c == 1) {
if(bc > bd)
cout<<"AB//CD"<<'\n';
else
cout<<"AB//DC"<<'\n';
}
else {
if(ac < ad)
cout<<"AB//CD"<<'\n';
else
cout<<"AB//DC"<<'\n';
}
}
}
return 0;
}
H. Harder Gcd Problem
题意：数1~n最多能组成多少对不互质的数对
思路：逆序遍历小于 n 的所有素数，取出1~n中所有该素数的倍数，两两配对，如果是奇数个留下数 p * 2，因为这个数可以最后遍历2的倍数时配。比赛的时候没想到这一点，用优先队列维护的有效（还没有被遍历过）素因子最多的数，把这个数留下来，比较麻烦，但也不是很慢：
emm还是用正解做吧：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int pri[N], tot;
bool vis[N], is[N];
void init() {
memset(vis, 0, sizeof(vis));
vis[0] = vis[1] = 1;
tot = 0;
for(int i = 2; i < N; ++i) {
if(!vis[i]) {
pri[++tot] = i;
for(int j = i + i; j < N; j += i)
vis[j] = 1;
}
}
}
int main() {
init();
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int it = upper_bound(pri + 1, pri + tot + 1, n) - pri- 1;
vector<int>vec;
memset(is, 0, sizeof(is));
for(int i = it; i >= 1; --i) {
int cnt = 1;
is[pri[i]] = 1;
vec.push_back(pri[i]);
for(int j = pri[i] * 3; j <= n; j += pri[i]) {
if(!is[j]) {
is[j] = 1;
cnt++;
vec.push_back(j);
}
}
if(cnt & 1) {
if(pri[i] * 2 <= n && !is[pri[i] * 2]) {
vec.push_back(pri[i] * 2);
is[pri[i] * 2] = 1;
}
else
vec.pop_back();
}
}
int ans = vec.size() / 2;
cout<<ans<<'\n';
for(int i = 0; i < ans * 2; i += 2)
cout<<vec[i]<<' '<<vec[i + 1]<<'\n';
vec.clear();
}
return 0;
}
