题解 P6583 【回首过去】

_Atyou · 2020-06-01 22:05:11 · 题解

算法：整除分块

Part 1 - Subtask1 (40分)

分析一下 \frac{x}{y} 可以表示为十进制有限小数的条件 :

若 \frac{x}{y} 可以表示为十进制有限小数，则存在 k 使得 \frac{x \times 10^{k}}{y} 为整数。

考虑 \frac{x}{y} 最简的情况（不是最简的可以化成最简）的情况下， x 和 y 已不含相同质因子，则 y 在只含质因子 2 或 5 的情况下， \frac{x}{y} 可以表示为十进制有限小数。

于是可以 O(n^2) 枚举 x 和 y ，先约分，再判断 y 是否只含质因子 2 或 5 即可。

复杂度貌似是 O(n^2\log n)

Part 2 - Subtask2 (80分)

考虑对于 y ，x 满足包含 y 除了 2 或 5 之外的所有质因子，且每个质因子的个数大于等于 y 中该质因子的个数。简单来说，就是 y 去掉质因子 2 或 5 之后， x 是 y 的倍数。

对于每个 y，这样的 x 为 \lfloor \frac{n}{\frac{y}{2^α \times 5^β}} \rfloor 个。则题目变成统计 \sum_{i=1}^n \lfloor \frac{n}{\frac{i}{2^α \times 5^β}} \rfloor， α 和 β 对应 i 中 2 和 5 的质因子个数。

复杂度貌似是 O(n\log n)

Part 3 - Subtask3 (100分)

前置知识 ： 整除分块（已补充于文章结尾，已经掌握的可以忽略，并确保掌握后再阅读 Part 3 的内容）

考虑更快的计算 \sum_{i=1}^n \lfloor \frac{n}{\frac{i}{2^α \times 5^β}} \rfloor 这个式子。感觉它很像能整除分块的形式 \sum \lfloor \frac{n}{i} \rfloor。

令 \frac{i}{2^α \times 5^β}=t ，就差不多能用整除分块来处理了。

但注意这里 t 是有限制条件的 :

1. t \times 2^α \times 5^β = i \le n$ 得到 $t \le \lfloor \frac{n}{2^α \times 5^β} \rfloor
2. t$ 不含质因子 $2$ 和 $5

则题目变成枚举 α 和 β 利用整除分块快速统计 \sum_{t=1}^{\lfloor \frac{n}{2^α \times 5^β} \rfloor } \lfloor \frac{n}{t} \rfloor 再累加即可。

至于怎么枚举 α 和 β ， 发挥对数的功底即可。（具体可参考程序里的循环语句，对应 i 和 j）

至于怎么剔除含质因子 2 和 5 的数，用容斥原理即可。（具体可参考程序里的 calc 函数）

复杂度算不太懂，貌似是 O(\sqrt n + \log^3 n)

补充 ： 其实可以发现枚举 α 和 β 时改变的只是整除分块 t 的上限，所以可以优先处理出整除分块的分块端点和前缀和，要统计时直接利用二分，加上完整块的和，再补上不完整的一部分即可。这样去掉了枚举 α 和 β 里整除分块的那层循环，用二分降下时间复杂度，才得以顺利通过此题。

Part 3 code ：

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

const int MAXN = 2000000 + 5;

typedef long long LL;

LL power(LL a, LL b) {
    LL ans = 1;
    for (; b; b >>= 1, a *= a)
        if (b & 1) ans *= a;
    return ans;
}

LL n, ans, pos[MAXN], sum[MAXN];

LL calc(LL l, LL r) {
    return (r - l + 1 - r / 2 + (l - 1) / 2 - r / 5 + (l - 1) / 5 + r / 10 - (l - 1) /  10);
}

int main() {
    cin >> n;
    int cnt = 0;
    for (LL l = 1, r; l <= n; l = r + 1) {
        pos[++cnt] = r = n / (n / l);
        sum[cnt] = sum[cnt - 1] + calc(l, r) * (n / l);
    }
    int p2 = log(n) / log(2); LL t1 = power(2, p2); 
    for (int i = p2; i >= 0; --i, t1 /= 2) {
        int p5 = log(n / t1) / log(5); LL t2 = power(5, p5);
        for (int j = p5; j >= 0; --j, t2 /= 5) {
            LL lim = n / t1 / t2;
            int x = lower_bound(pos + 1, pos + cnt + 1, lim) - pos - 1;
            ans += sum[x] + calc(pos[x] + 1, lim) * (n / lim);
        }
    }
    cout << ans << endl;
    return 0;
}

Part X : 整除分块

有些时候会遇上形如 \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor 的式子， O(n) 是最显而易见的统计方法。

但当 n 的值很大的时候， O(n) 显然不能满足需要。

考虑用 O(n) 的方式打表找找关于 \lfloor \frac{n}{i} \rfloor 的规律。

当 n=10 时，大概是这样的

可以发现有许多相等的 \lfloor \frac{n}{i} \rfloor连在一块，形象来说成块状分布。

于是我们针对那些\lfloor \frac{n}{i} \rfloor相等的块，确定左右端点 l 和 r，就可以分块处理了。对于每个块的总和是 (r-l+1) \times \lfloor \frac{n}{i} \rfloor

左端点只要在上一个块的右端点上加 1 即可，而右端点是对于 \lfloor \frac{n}{i} \rfloor 最大的 i, 可以发现为 r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor (可以自己尝试证明)

对于 \lfloor \frac{n}{i} \rfloor 最多只有 2 \sqrt n 种取值，所以整除分块的时间复杂度是 O( \sqrt n )

Part X code :

for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}