GESP202603 五级

GESP202603 五级

一. 有限不循环小数

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

2 11

输出 #1

5

说明/提示

样例解释

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

数据范围

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

---

思路如下：

1. 对于$\frac{1}{a}$是一个不循环小数
   (1). $a=1$，显然$\frac{1}{a}=1$。
   (2). $a>=2$，若$\frac{1}{a}$是有限小数，即存在正整数$k$使得
   $$\frac{1}{a}=\frac{N}{10^k},(N\in Z^{+})$$
   即:
   $$10^k=a\ast N$$
   即:
   $$a\mid 10^k$$
   即:
   $$a\mid 2^k\ast 5^k$$
   由算术基本定理可知:
   $$a=p_1^{{\alpha }_1}\ast p_2^{{\alpha }_2}\ast ...\ast p_k^{{\alpha }_k}(a>1,p_i\in P)$$
   即:
   $$p_1^{{\alpha }_1}\ast p_2^{{\alpha }_2}\ast ...\ast p_k^{{\alpha }_k}\mid 2^k\ast 5^k$$
   显然，$a$中必然只能包含质因子$2$或者$5$

解法1(质因数分解)

步骤

1. 枚举$i$从$L$到$R$
2. 将$i$进行质因数分解，检查是否存在 $2$ 和 $5$ 以外的质因子。

时间复杂度$O(R\sqrt{R}$）

#include <bits/stdc++.h>
using namespace std;
bool fac(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        while (n % i == 0) {
            n /= i;
            if (i != 2 && i != 5) return false;
        }
    }
    if (n > 1 && n != 2 && n != 5) return false;
    return true;
}

int main() {
    int L, R, ans = 0;
    cin >> L >> R;
    for (int i = L; i <= R; i++) {
        if (fac(i)) ++ans;
    }
    cout << ans << endl;
    return 0;
}

解法2(直接分解$2$和$5$)

步骤

1. 枚举$i$从$L$到$R$
2. 由于我们已经证明出$i$中只能包含$2$和$5$质因子,可以直接从i中分解所有的$2$和$5$，判断最后是否为1。
   时间复杂度$O(RlogR$）

#include <bits/stdc++.h>
using namespace std;
bool fac(int n) {
    while (n % 2 == 0) n /= 2;
    while (n % 5 == 0) n /= 5;
    return n == 1;
}

int main() {
    int L, R, ans = 0;
    cin >> L >> R;
    for (int i = L; i <= R; i++) {
        if (fac(i)) ++ans;
    }
    cout << ans << endl;
    return 0;
}

解法3(构造法)

由于终止数只能包含质因子 $2$ 和 $5$，因此所有终止数均为形如 $2^x\ast 5^y$ 的数（$x,y\ge 0$）。我们可以直接枚举不超过 $R$ 的此类数，统计落在 $[L,R]$ 内的个数。
时间复杂度为 $O({\log }_{2}R\times {\log }_{5}R)$，远优于 $O(RlogR)$ 的枚举方法。

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

int main() {
    int L, R, ans = 0;
    cin >> L >> R;
    for (int x = 1; x <= R; x *= 2) {        // 枚举 2 的幂
        for (int y = x; y <= R; y *= 5) {    // 在 2 的幂基础上乘 5 的幂
            if (y >= L) ans++;
        }
    }
    
    cout << ans << endl;
    return 0;
}

---

二. 找数

题目描述

给定一个包含 $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

输入 #1

3 5
4 2 3
3 1 5 4 6

输出 #1

2

说明/提示

样例解释

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

数据范围

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

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

解法1(map或者哈希)

思路：

1. 将数组$a$中数据存入map容器。
2. 遍历数组 $b$，判断当前元素是否在容器中，若是则计数加一。

map的时间复杂度$O((m+n)logn)$，哈希时间复杂度$O(m+n)$
$注意：由于1\le a_i,b_i\le 10^9,直接使用桶，空间上无法接受，可以使用map或者unordered\_map$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
map<int, int> mp;
unordered_map<int, int> mp2;
int main() {
    int x, n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        mp[x]++;
    }
    for (int i = 1; i <= m; i++) {
        cin >> x;
        if (mp[x]) ans++;
    }
    cout << ans << endl;
    return 0;
}

解法2(排序+二分查找)

思路：

1. 将$a$数组进行排序
2. 遍历数组 $b$，对每个元素在 $a$ 中二分查找是否存在。。

时间复杂度$O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
int main() {
    int x, n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= m; i++) {
        cin >> x;
        // 使用binary_search函数判断x是否存在
        if (binary_search(a, a + n + 1, x)) ++ans;
        // 使用lower_bound定位大于等于x位置
        //if (*lower_bound(a + 1, a + n + 1, x) == x) ++ans;
    }
    cout << ans << endl;
    return 0;
}

解法3(排序+双指针)

思路：

1. 将$a$数组和$b$数组进行排序
2. 使用双指针同时遍历两个有序数组，统计相同元素个数。

时间复杂度$O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], b[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    int i = 1, j = 1, ans = 0;
    while (i <= n && j <= m) {
        if (a[i] == b[j]) {  // 相等计数
            ans++;
            i++;
            j++;
        } else if (a[i] < b[j]) {  // a小，a往尝试
            i++;
        } else {           // b小，b往后尝试
            j++;
        }
    }
    cout << ans << endl;
    return 0;
}