202603-1 有限不循环小数#

题目描述

若 $\frac{1}{a}$ 可化为一个有限的，不循环的小数，则称 $a$ 为终止数。

请你求出在 $L$ 到 $R$ 中终止数的数量。

输入格式

输入一行，包含两个整数 $L,R$。

输出格式

输出一行，包含一个整数，表示 $L$ 到 $R$ 中终止数的数量。

样例输入 1

2 11

样例输出 1

5

提示

【样例解释】

在 $[2,11]$ 终止数有 $2$、$4$、$5$、$8$、$10$。

【数据范围】

保证 $1 \le L \le R \le 10^6$。

代码解析

这道题代码很简单，考察的重点是数论，一个数字如果是终止数，那么它的质因子只能有 $2$ 和 $5$，通过题目给出的 2、4、5、8、10 花点时间思考也可以找到这个规律，所有我们只需要判断每个数字是否只包含 $2$ 和 $5$ 这两个质因子即可。

1
#include <bits/stdc++.h>
2
using namespace std;
3
bool check(int a) {
4
    while (a % 2 == 0) a /= 2;
5
    while (a % 5 == 0) a /= 5;
6
    if (a == 1) return true;
7
    return false;
8
}
9
int main() {
10

11
    int l, r, cnt = 0;
12
    cin >> l >> r;
13
    for (int i = l; i <= r; i++)
14
        if (check(i))
15
            cnt++;
16
    cout << cnt;
17

18
    return 0;
19
}

202603-2 找数#

题目描述

给定一个包含 $n$ 个互不相同的正整数的数组 $A$ 与一个包含 $m$ 个互不相同的正整数的数组 $B$，请你帮忙计算有多少个数在数组 $A$ 与数组 $B$ 中均出现。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 表示数组 $A$。

第三行包含 $m$ 个正整数 $b_1,b_2,\cdots,b_m$ 表示数组 $B$。

输出格式

输出一个整数，表示在数组 $A$ 与数组 $B$ 中均出现的数的个数。

样例输入 1

3 5
4 2 3
3 1 5 4 6

样例输出 1

2

提示

【样例解释】

样例 1 中，$4$、$3$ 在数组 $A$ 与 $B$ 中均出现。

【数据范围】

对于 $40\%$ 的数据，保证 $1 \leq n,m \leq 1000$。

对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 10^5$，$1 \leq a_i,b_i \leq 10^9$。

代码解析

这道题代码也很简单，我们先将数组 $A$ 排序，然后对于数组 $B$ 中的每个数 $b$，我们使用二分查找在数组 $A$ 中查找是否存在 $b$，如果存在，那么 $b$ 就是在数组 $A$ 与数组 $B$ 中均出现的数。

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int n, m, a[100005], cnt = 0;
6
    cin >> n >> m;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    sort(a, a+n);
10
    int b;
11
    for (int j = 0; j < m; j++){
12
        cin >> b;
13
        if (a[lower_bound(a, a+n, b)-a] == b)
14
            cnt++;
15
    }
16
    cout << cnt;
17

18
    return 0;
19
}