题单

Notes

略。

Problems

A. 青蛙的约会

题目很经典, 题意在此不表。

因为跳跃时间是相同的, 则有下列方程:

用 exgcd 解之即可。

int exgcd(int a, int b, int64_t &x, int64_t &y) {
  if (!b) {
    return x = 1, y = 0, a;
  }
  int gcd = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return gcd;
}

int a, b, m, n, l;
std::cin >> a >> b >> m >> n >> l;

int64_t x = 0, y = 0;
int gcd = exgcd(m - n, l, x, y);
if ((b - a) % gcd) {
  std::cout << "Impossible\n";
} else {
  x *= (b - a) / gcd;
  int64_t t = std::abs(l / gcd);
  std::cout << (x % t + t) % t << '\n';
}

B. Sum of Consecutive Prime Numbers

给出一个数, 问有多少种将其分解为连续的素数之和的方案。

这个题数据很大，注释掉的做法（预处理）挂了，写了个双指针。

不知道二分能不能过。

#include <bits/stdc++.h>

static const int N = 40000010;

bool st[N];
int p[N], cnt = 0;
int sum[N];

int main() {
  for (int i = 2; i <= N; ++i) {
    if (!st[i])
      p[cnt++] = i;
    for (int j = 0; p[j] <= N / i; ++j) {
      st[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
    }
  }

  // for (int i = 0; i < cnt; ++i) {
  //   int partial = 0;
  //   for (int j = i; j < cnt; ++j) {
  //     partial += p[j];
  //     if (partial > N)
  //       break;
  //     sum[partial]++;
  //   }
  // }

  int n, t;
  std::cin >> t;
  while (t--) {
    std::cin >> n;
    // std::cout << sum[n] << '\n';
    int cnt = 0, partial = 0, l = 0, r = 0;
    while (true) {
      if (n == partial)
        ++cnt;
      if (n <= partial)
        partial -= p[l++];
      else {
        partial += p[r];
        if (p[r] > n)
          break;
        ++r;
      }
    }
    std::cout << cnt << '\n';
  }
  return 0 ^ 0;
}

C. 质数距离

题意大概是这样：我们定义两个相邻质数之间的距离为「质数距离」，现在给定一个区间(给定左右端点)，求在此区间内最小和最大的质数距离。如果有多个，输出第一个。

• 制约：$1\le L\le R\le 2^{31}-1,R-L\le 10^{6}1\backslash le\; L\backslash le\; R\; \backslash le\; 2^\{31\}\; -\; 1,\; \backslash quad\; R\; -\; L\; \backslash le\; 10^6$

• $2^{31}-12^\{31\}\; -\; 1$，也即INT_MAX，大概是$2\cdot 10^{9}2\backslash cdot10^9$ (2,147,483,647)。空间不够，并且即使强大如线性筛也不能够在$1s1s$内完成，并且由于递推关系，不能单筛一个区间。注意到$R-L\le 10^{6}R-L\backslash le\; 10^6$，这里实际上提示了我们数组大小(应当在这么长的数组上进行操作)。
• 因子成对出现。且对于一个数$NN$，至少有一个$\le \sqrt{N}\backslash le\; \backslash sqrt\; N$的质因子，最多有一个$\ge \sqrt{N}\backslash ge\; \backslash sqrt\; N$的质因子。这意味着我们可以只找出 $\sqrt{N}\backslash sqrt\; N$ 个质因子，这个复杂度是$\mathcal{O}(\sqrt{N})\backslash mathcal\; O(\backslash sqrt\; N)$，$\sqrt{2\cdot 10^9}\doteq 46400\backslash sqrt\; \{2\backslash cdot10^9\}\; \backslash doteq\; 46400$。
• 接着我们使用这些质因子将$[L,R][L,R]$中的合数都筛掉，最大的花费是

$10^6\cdot ({\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{3}}+{\displaystyle \frac{1}{5}}+{\displaystyle \frac{1}{7}}+\cdots +{\displaystyle \frac{1}{\sqrt{N}}})=10^6\cdot \log \log \sqrt{N}\doteq 10^{6}10^6\backslash cdot\; \backslash Big(\backslash dfrac\{1\}\{2\}+\backslash dfrac\{1\}\{3\}+\backslash dfrac\{1\}\{5\}+\backslash dfrac\{1\}\{7\}+\backslash cdots+\backslash dfrac\{1\}\{\backslash sqrt\; N\}\; \backslash Big)\; =\; 10^6\backslash cdot\backslash log\backslash log\backslash sqrt\; N\backslash doteq10^6$

这里使用到了埃氏筛时间复杂度分析技巧：质数意义下的调和级数收敛于$\log \log n\backslash log\backslash log\; n$

• 同时这一步中，大于$LL$的第一个合数是 $p_0=p\cdot \lceil {\displaystyle \frac{L}{p}}\rceil =p\cdot \lfloor {\displaystyle \frac{L+p-1}{p}}\rfloor ,\mathrm{其}\mathrm{中}{p}_0>2pp\_0\; =\; p\backslash cdot\backslash lceil\backslash dfrac\{L\}\{p\}\backslash rceil\; =\; p\backslash cdot\backslash lfloor\backslash dfrac\{L+p-1\}\{p\}\backslash rfloor,其中p\_0>2p$ 后者不需要调用库函数。

• 因此，我们可以在$\mathrm{O}(\sqrt{N}+10^6)\backslash Omicron(\backslash sqrt\; N\; +\; 10^6)$时间内解决这道题

#include <bits/stdc++.h>

using ll = long long;
static const int N = 46500;

bool st[N];
ll cnt, p[N];
void get_p(ll n) {
  for (int i = 2; i <= n; ++i) {
    if (!st[i])
      p[cnt++] = i;
    for (ll j = 0; p[j] <= n / i; ++j) {
      st[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
    }
  }
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);

  get_p(N - 1);

  int l, r, t;
  std::cin >> t;
  while (t--) {
    std::cin >> l >> r;
    std::bitset<1000010> vis;
    std::vector<int> ps;
    for (int i = 0; i < cnt; ++i) {
      ll &pi = p[i];
      for (ll j = std::max(pi << 1, (l + pi - 1) / pi * pi); j <= r; j += pi)
        vis[j - l] = true;
    }
    for (int i = 0; i <= r - l; ++i) {
      if (!vis[i] && i + l > 1)
        ps.push_back(i + l);
    }
    if (ps.size() < 2) {
      std::cout << "There are no adjacent primes.\n";
    } else {
      int m = 0, M = 0;
      for (int i = 0; i < ps.size() - 1; ++i) {
        int dist = ps[i + 1] - ps[i];
        if (dist < ps[m + 1] - ps[m])
          m = i;
        if (dist > ps[M + 1] - ps[M])
          M = i;
      }
      std::cout << ps[m] << "," << ps[m + 1] << " are closest, "
                << ps[M] << "," << ps[M + 1] << " are most distant.\n";
    }
  }

  return 0;
}

D. Prime Land

给定 $NN$ 输出 $N-1N\; -\; 1$， 均以唯一分解给出。

分解质因数即可。

#include <bits/stdc++.h>

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int tt;
  std::cin >> tt;
  while (tt--) {
    int k;
    std::cin >> k;
    auto N = 1LL;
    for (int i = 0, p, e; i < k; ++i) {
      std::cin >> p >> e;
      while (e--) {
        N *= p;
      }
    }
    N -= 1;
    std::vector<std::pair<int, int>> ans;
    int n = 0;
    for (int i = 2; i * i <= N; ++i)
      if (N % i == 0) {
        int cnt = 0;
        while (N % i == 0) {
          ++cnt;
          N /= i;
        }
        ans.emplace_back(i, cnt);
      }
    if (N != 1)
      ans.emplace_back(N, 1);
    for (auto it = ans.rbegin(); it != ans.rend(); ++it) {
      auto [x, y] = *it;
      std::cout << x << ' ' << y << " \n"[it == ans.rend() - 1];
    }
  }
  return 0 ^ 0;
}

E. X-factor Chains

题意: 给定一个数 $xx$, 求出最长的一条链, 使得 $p_0\mid p_1\mid p_2\mid \cdots \mid xp\_0\; \backslash mid\; p\_1\; \backslash mid\; p\_2\; \backslash mid\; \backslash cdots\; \backslash mid\; x$ （共 $m+1m\; +\; 1$ 个互异的数）。

输出最大的 $mm$，以及对应长度链的条数。

解答: 考虑哈斯图（或者从唯一分解的角度来看也可以）。要使得这条链更长，那么两个链节之间一定是差一个素数（乘积）。因此，我们找出所有的质因子。其个数即为 $mm$。

至于方案数, 是一个调整链节的顺序的过程，由于元素之间互异，因此为多重集的组合数 click this link to learn about it.

注意质因子不会超过 ${}_2(\max \{N\})\backslash log\_2(\backslash max\backslash \{N\backslash \})$ 个。

#include <bits/stdc++.h>

static const int N = 1000010;

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  std::vector<int> p(N + 1, 0);
  std::vector<bool> st(N + 1, false);
  int cnt = 0;

  for (int i = 2; i <= N; ++i) {
    if (!st[i])
      p[cnt++] = i;
    for (int j = 0; p[j] <= N / i; ++j) {
      st[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
    }
  }

  int64_t fac[31] = { 1, };
  for (int i = 1; i <= 30; ++i) {
    fac[i] = i * fac[i - 1];
  }

  int tt;
  std::cin >> tt;
  while (tt--) {
    int N;
    std::cin >> N;

    std::vector<int> ans;

    for (int i = 0; 1LL * p[i] * p[i] <= N; ++i)
      if (N % p[i] == 0) {
        int cnt = 0;
        while (N % p[i] == 0) {
          ++cnt;
          N /= p[i];
        }
        ans.push_back(cnt);
      }
    if (N != 1)
      ans.push_back(1);

    int sum = std::accumulate(ans.begin(), ans.end(), 0);
    int64_t res = fac[sum];
    for (auto i : ans) {
      res /= fac[i];
    }
    std::cout << sum << ' ' << res << '\n'; 
  }

  return 0 ^ 0;
}

总结

略。