[Luogu]P6583 回首过去
本文最后更新于 237 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp6583/

题意

题目传送门

给定正整数 $n$,求出有序整数对 $(x,y)$ 的个数,满足 $1 \leq x,y \leq n$ 且 $\frac{x}{y}$​ 可以表示为十进制有限小数。

思路

先观察题目。
考虑如何表示为十进制有限小数,发现分母为 $10$ 时成立。
而 $10$ 的因子: $2,5$ 的倍数做分母时,分子任意都成立。
那么对于一个分数,化简后判断分母是否能表示为 $2^a \times 5 ^ b$ 的形式,若能则计入。

暴力做法

根据这些性质,可以写出题面中提到的 $O(n^2)$ 暴力了。
枚举 $x,y$,化简后再判断分母是否为 $1$。

for (int x = 1; x <= n; ++x)
    for (int y = 1; y <= n; ++y)
    {
        int g = gcd(x,y), a = x / g, b = y / g;
        while (b % 2 == 0)
            b /= 2;
        while (b % 5 == 0)
            b /= 5;
        if (b == 1) ++ans;
    }

可以通过 Subtask 1。

优化做法

再深入观察性质,发现当 $x,y$ 中的一个确定时,另一个能取的方案数可以直接统计出来。

由此可以写出 $O(n)$做法。

考虑枚举 $y$,设 $y = 2 ^ a \times 5 ^ b \times c$。

其中 $c$ 是一个与 $2,5$ 互质的数。

由于分母中可以保留 $2 ^ a \times 5 ^ b$,只需要将 $c$ 约去即可。
也就是说,分子只要是 $c$ 的倍数,就能满足条件。

$$\frac{x}{y} = \frac{c \times k}{2 ^ a \times 5 ^ b \times c} = \frac{k}{2 ^ a \times 5 ^ b}$$

那么将枚举得到的 $y$ 中 $2,5$ 除尽得到 $c$,再统计 $[1,n]$ 中有多少个 $c$ 的倍数即可。

inline int getC(int y)
{
    while(y % 2 == 0)
        y /= 2;
    while(y % 5 == 0)
        y /= 5;
    return y;
}

不难发现,$[1,n]$ 的范围中有 $\lfloor \frac{n}{c} \rfloor$ 个 $c$ 的倍数。

for(int y = 1;y<=n;++y)
    ans += n / getC(y);

于是我们就打出了一个比暴力还短的 $O(n)$ 的代码。

继续优化

然而想要通过 $10^{12}$ 级别的数据,需要更快的算法。
可以用整除分块的方法来优化。

观察 $\lfloor \frac{n}{c} \rfloor$,发现对于某一段连续的 $c$,这个商是一定的。
因此我们可以用整除分块,处理出这段商连续的 $c$ 的左右端点,统计其中满足条件的 $c$ 的个数。

先考虑如何统计某段连续 $c$ 中满足条件的个数。
可以统计 $[1,R]$ 与 $[1,L-1]$ 的个数,然后做差。

对于 $c \in [1,R] $,$c$ 与 $2,5$ 互质即满足条件,因此可以减去 $2,5$ 的倍数的个数。
再加上重复减的 $10$ 的倍数即可。

inline int getNum(int C)
{
    return C - C / 2 - C / 5 + C / 10;
}

整除分块如何处理呢?

for(int l = 1;l <= n;l = r + 1)
{
    k = n / l, r = n / k;
    ....
}

枚举连续的 $c$ 的区间 $[l,r]$,满足 $k = \lfloor \frac{n}{c} \rfloor$ 都相等。
那么其中每个合法的 $c$ 都有 $k$ 个倍数。
然而 $y = 2 ^ a \times 5 ^ b \times c$,还需要确定 $2 ^ a \times 5 ^ b$ 有几种取法,随后使用乘法原理。
可以预处理出所有的 $A = 2 ^ a \times 5 ^ b$,排序后利用单调性判断有多少 $A$ 个满足 $A \times c \leq n$,即 $A \leq k$。
由于枚举过程中 $c$ 不断增大,满足的 $A$ 的数量会不断减小,利用单调性在枚举时维护一下即可。
对于一段 $[l,r]$ 区间中的 $c$,将 $[1,m]$ 中符合要求的 $c$ 个数记为 $s_m$,满足条件的 $A$ 的数量记为 $tot$,则对答案的贡献为:

$$k \times (s_r – s_{l-1}) \times tot$$

Code

代码实现难度不大。

#include <cstdio>
#include <algorithm>
template <typename T>
void read(T &r)
{
    static char c;r = 0;
    for (c = getchar(); c > '9' || c < '0'; c = getchar());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
}
const int maxn = 1000000;
long long n, ans;
long long A[maxn], tot;
inline long long calc(long long x){return x - x / 2 - x / 5 + x / 10;}
int main()
{
    read(n);
    for (long long i = 1; i <= n; i <<= 1)
        for (long long j = 1; i * j <= n; j *= 5)
            A[++tot] = i * j;
    std::sort(A + 1, A + 1 + tot);
    long long l, r, k;
    for (long long l = 1; l <= n; l = r + 1)
    {
        k = n / l, r = n / k;
        while (A[tot] > k && tot) --tot;
        ans = ans + k * (calc(r) - calc(l - 1)) * tot;
    }
    printf("%lld", ans);
    return 0;
}
本文标题:[Luogu]P6583 回首过去
本文作者:Clouder
本文链接: https://www.codein.icu/lp6583/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇