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

B Basic Gcd Problem

题意：

给出

举个例子：

继续递推下去：

即：

就是看 的贡献，也就是

AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mxn = 1000010, mo = 1000000007;
int p[mxn], lo[mxn], t;
bool vis[mxn];

ll pw(ll a, ll b)
{
  ll r = 1;
  while (b)
  {
    if (b & 1)
      r = r * a % mo;
    a = a * a % mo;
    b >>= 1;
  }
  return r;
}
void shai(int n)
{
  t = 0;
  vis[1] = 1;
  for (int i = 2; i <= n; i++)
  {
    if (!vis[i])
    {
      p[++t] = i;
      lo[i] = i;
    }
    for (int j = 1; j <= t && p[j] * i <= n; j++)
    {
      vis[p[j] * i] = 1;
      lo[p[j] * i] = p[j];
      if (i % p[j] == 0)
        break;
    }
  }
}
int main()
{
  int T, n, c;
  shai(1000000);
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &c);
    int cnt = 0;
    while (n > 1)
    {
      int x = lo[n];
      n /= x;
      cnt++;
    }
    int ans = pw(c, cnt);
    printf("%d\n", ans);
  }
  return 0;
}

F Finding the Order

题意：

给出两条平行线 跟 ， 上有 两点， 在 的左边， 上有 两点但 两点的相对位置不知道，给出 的长度，判断 在

分情况讨论就行了。

AC代码：

int main()
{
    int t;
    sd(t);
    while (t--)
    {
        int ac, ad, bc, bd;
        sdd(ac, ad);
        sdd(bc, bd);
        if (bc == bd)
        {
            if (ad > ac)
                puts("AB//CD");
            else
                puts("AB//DC");
        }
        else if (bd > bc)
        {
            if (ad > ac)
                puts("AB//CD");
            else
                puts("AB//DC");
        }
        else
        {
            if (ac > ad)
                puts("AB//DC");
            else
                puts("AB//CD");
        }
    }
    return 0;
}

H Harder Gcd Problem

题意：

有 个苹果，编号为 。现要将苹果组成若干对，每对苹果最小公约数不为

把 中的数先预处理里出来他们的最小质因子，把 所有数的最小质因子存起来，从大到小遍历，是当前质因子倍数个数偶数的直接两两分组，奇数的最小的那个可以判断他的一倍和二倍是否可以匹配，最后看看

AC代码：

const int N = 5e5 + 50;
int zyz[N], prim[N], cnt = 0, vis[N];
vector<int> v[N];

void init(int n)
{
  rep(i, 2, n)
  {
    if (!zyz[i])
      prim[++cnt] = i;
    for (int j = i; j <= n; j += i)
      if (!zyz[j])
        zyz[j] = i;
  }
}

void get_pos(int n)
{
  rep(i, 1, n)
  {
    if (zyz[i])
    {
      int pos = lower_bound(prim + 1, prim + cnt + 1, zyz[i]) - prim; //每个数最小质因子的的位置
      v[pos].pb(i);
    }
  }
}

int main()
{
  int t;
  sd(t);
  init(200010);
  while (t--)
  {
    int n;
    sd(n);
    rep(i, 1, n)
    {
      v[i].clear();
      vis[i] = 0;
    }
    get_pos(n);
    int pos = upper_bound(prim + 1, prim + cnt + 1, n) - prim;
    pos--;
    vector<PII> ans;
    per(i, pos, 1)
    {
      if (i == 1)
      {
        vector<int> res;
        res.clear();
        for (auto i : v[i])
          if (!vis[i])
            res.pb(i);
        for (int j = 0; j < res.size(); j += 2)
          if (j + 1 < res.size())
            ans.pb(make_pair(res[j], res[j + 1]));
      }
      else
      {
        int len = v[i].size();
        if (len % 2 == 0)
        {
          for (int j = 0; j < len; j += 2)
          {
            if (j + 1 < len)
              ans.pb(make_pair(v[i][j], v[i][j + 1]));
            vis[v[i][j]] = 1;
            vis[v[i][j + 1]] = 1;
          }
        }
        else
        {
          for (int j = 1; j < len; j += 2)
          {
            if (j + 1 < len)
              ans.pb(make_pair(v[i][j], v[i][j + 1]));
            vis[v[i][j]] = 1;
            vis[v[i][j + 1]] = 1;
          }
          if (2 * v[i][0] <= n)
          {
            ans.pb(make_pair(v[i][0], 2 * v[i][0]));
            vis[v[i][0]] = 1;
            vis[2 * v[i][0]] = 1;
          }
        }
      } 
    }
    pd(ans.size());
    for (auto i : ans)
      pdd(i.fi, i.se);
  }
  return 0;
}