2020牛客暑期多校训练营（第四场）

比赛地址：

https://ac.nowcoder.com/acm/contest/5669

擦，这就第四场了,前几场题目还没补QAQ,这几天赶快补一下。

B Basic Gcd Problem

题目地址：

https://ac.nowcoder.com/acm/contest/5669/B

基本思路:

这题我们理解题意其实就比较简单了,
关键是要弄清楚题目中给出的这串式子的实际意义,
其实我们稍微分析其实就能发现，这个要找到后面的最大值，
其实就是找这个,不断的和其他数变为要的最大次数,然后这个最大值就是;
然后变为要的最大次数，这个我们根据唯一分解定理，就能知道如果每次我只掉的一个质因子，显然这样次数最多，那么质因子的个数就是这个最大次数了。
所以整理一下，就是求质因子的个数，然后就是答案,预先筛一下素数，就能很快的质因数分解了;

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int mod  = 1e9 + 7;
int qpow(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}

const int maxn = 1e6 + 10;
int prime[maxn];
bool is_prime[maxn];

int sieve(int n) {
  int p = 0;
  for (int i = 0; i <= n; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime[p++] = i;
      for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
  }
  return p;
}

int num;
map<int,int> prime_factor(int n) {
  map<int, int> res;
  for (int i = 0; prime[i] * prime[i] <= n && i < num; i++) {
    while (n % prime[i] == 0) {
      ++res[prime[i]];
      n /= prime[i];
    }
  }
  if (n != 1) res[n] = 1;
  return res;
}

int n,c;
signed main() {
  IO;
  num = sieve(1000010);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> c;
    map<int, int> res = prime_factor(n);
    int cnt = 0;
    for(auto it : res) cnt += it.second;
    int ans = qpow(c,cnt);
    cout << ans << '\n';
  }
  return 0;
}

H Harder Gcd Problem

题目地址：

https://ac.nowcoder.com/acm/contest/5669/H

基本题意：

感觉题面写的复杂了,其实就是让我们在范围那尽量多的挑选两两不为的数对,并且内每个数只能用一次。

基本思路：

我们考虑想一种构造方法，能构造出最多的这个数对。
首先我们是肯定不能用的，首先排除,
然后我们知道大于的质数，肯定也找不出一个大于它小于又不和它互质的数,
所以我们只要对范围内的每个质数考虑构造方法,
这里我们先将留下后面再使用，然后枚举范围内的每个质数,
对于每个质数，我们先留不用,在范围内找还未使用的,
然后我们可以反向枚举(不反向也可以，只是留方便一点)将这些未使用的两两匹配成一个答案数对，
但是如果是奇数，由于反向枚举那么两两匹配就会剩下，所以这时再将和前面预留的配对。
最后，我们知道上述过程中的们有些被使用了,而有些却没有,但他们都是的倍数，
所以我们之前预留的又有用了,我们再将的倍数里未被使用的部分两两匹配。
比较容易发现这种贪心构造思路能构造出最多数对。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 2e5 + 10;
int a[maxn];
bool vis[maxn], b[maxn];
signed main() {
  int t;
  cin >> t;
  for (int i = 2; i < maxn; i++) { // 素数筛;
    if (vis[i]) continue;
    for (int j = 2 * i; j < maxn; j += i) vis[j] = true;
  }
  while (t--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) b[i] = false;
    vector<pii > ans;
    for (int i = n / 2; i > 2; i--) { //找[3,n/2]范围内的所有质数p;
      if (!vis[i]) {
        int c = 0, j;
        for (j = i; j <= n; j += i) {
          if (j == 2ll * i) continue; //留一个2p给奇数个剩下那个;
          if (!b[j]) a[++c] = j;
        }
        for (j = c; j > 1; j -= 2) { //将p,3p,4p,5p...kp<=n里没使用过的都两两匹配;
          ans.emplace_back(mp(a[j], a[j - 1])), b[a[j]] = b[a[j - 1]] = true;
        }
        //奇数个就会剩下p和2p匹配;
        if (j == 1) ans.emplace_back(mp(a[j] * 2, a[j])), b[a[j] * 2] = b[a[j]] = true;
      }
    }
    int c = 0;
    //把剩下没匹配的2p也两两匹配;
    for (int j = 2; j <= n; j += 2) if (!b[j]) a[++c] = j;
    for (int j = c; j > 1; j -= 2) ans.emplace_back(mp(a[j], a[j - 1])), b[a[j]] = b[a[j - 1]] = true;
    cout << ans.size() << endl;
    for (auto it : ans)
      cout << it.first << ' ' << it.second << endl;
  }
  return 0;
}

F Finding the Order

题目地址：

https://ac.nowcoder.com/acm/contest/5669/F

基本思路：

比赛时疯狂分类讨论，然而我们其实比较容易证明，梯形的对角线之和必定大于两腰之和。
因此如果 那么就是否则。
ps.证明可见百度知道：https://zhidao.baidu.com/question/196726920.html

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

int a,b,c,d;
signed main() {
  IO;
  int t;
  cin >> t;
  while (t--) {
    cin >> a >> b >> c >> d;
    if(a + d < b + c) cout << "AB//CD" << '\n';
    else cout << "AB//DC" << '\n';
  }
  return 0;
}