题解 - [LightOJ 1341] Aladdin and the Flying Carpet

发表于 更新于 分类于 ， 本文字数： 91 阅读时长 ≈ 1 分钟

题目链接

简述题意

给定 \(a\) 和 \(b\), 输出所有满足下列条件的数对 \((c,d)\) 的个数

  1. \(cd=a\)
  2. \(b\leqslant c\leqslant d\)

解题思路

直接暴力求解会超时，我们可以先预处理素数表，这样就可以了

代码

Show code

LightOJ_1341view raw
1
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
const int N = 1e6 + 5;
int pri[N], cnt_pri;
bool vis[N];
int main() {
  for (int i = 2; i < N; ++i)
    if (!vis[i]) {
      pri[++cnt_pri] = i;
      for (int j = 2; i * j < N; ++j) vis[i * j] = 1;
    }
  int kase;
  scanf("%d", &kase);
  for (int cnt = 1; cnt <= kase; ++cnt) {
    i64 area, a;
    scanf("%lld%lld", &area, &a);
    if (area < a * a) {
      printf("Case %d: 0\n", cnt);
      continue;
    }
    i64 n = area, sum = 1;
    for (i64 i = 1, ans; i <= cnt_pri && pri[i] * pri[i] <= n; ++i) {
      if (!(n % pri[i])) {
        ans = 0;
        while (!(n % pri[i])) {
          ++ans;
          n /= pri[i];
        }
        sum *= ans + 1;
      }
    }
    sum >>= n <= 1;
    for (i64 i = 1; i < a; ++i)
      if (!(area % i)) sum--;
    printf("Case %d: %lld\n", cnt, sum);
  }
  return 0;
}