P6583 回首过去 (比扶苏短的做法

2333333333 考虑首先合法的答案一定是分数约分后分母的质因数只有 $2,5$。也就是说 $$ \frac{x}{y}=\frac{\frac{x}{\gcd(x,y)}}{2^p5^q} $$ 其中 $p,q$ 都是极大的。稍微化一下可以发现 $$ y=\gcd(x,y)\times 2^p5^q $$ 那么就可以对每一个 $y$ 求有多少个 $x$ 是合法的。考虑 $x$ 一定可以写作 $d\times \gcd(x,y)$，那么也就是说由于 $\gcd(x,y)$ 固定(因为 $2^p5^q$ 极大)要统计有多少个本质不同的 $d$ ，因为 $x$ 只能在 $[1,n]\cap \mathbb {Z_+}$ 中取值，所以不难发现一共有 $\left\lfloor\dfrac{n}{\gcd(x,y)}\right\rfloor$ 种取法。所以 $80$ 分可以这么写 ```cpp for (int i = 1 ; i <= n ; ++ i){ int j = i, o ; while (j % 2 == 0) j /= 2 ; while (j % 5 == 0) j /= 5 ; ans += n / j ; } ``` 考虑这个式子是一个下取整的形式，即 $$ \sum _{i=1}^n\left\lfloor\dfrac{n}{\zeta(i)}\right\rfloor \qquad(1) $$ 其中 $\zeta(i)$ 是最大的不含质因子 $2,5$ 的 $i$ 的因子。考虑调换枚举顺序，枚举 $\zeta(i)$，会有 $$ (1)=\sum_{k=1}^{n}\left\lfloor\dfrac{n}{k}\right\rfloor\times [2\nmid k]\times[5\nmid k]\times {\rm count(}\left\lfloor\dfrac{n}{k}\right\rfloor) $$ 其中最后一个 $\rm count(t)$ 表示 $1\sim t$ 之间有多少只包含 $2,5$ 作为质因数的数。原因很简单，因为我们枚举的是 $\zeta(i)$，$\zeta(i)$ 需要搭配上 $2^p5^q$ 才会有效，所以计数有多少 $\leq n$ 的数包含 $k$ 就是相当于计数有多少 $\leq \left\lfloor\dfrac{n}{k}\right\rfloor$ 的数包含 $2^p5^q$。于是这么做就是 $O(\sqrt n\log ^2 n)$ 的了。稍微预处理一下 $\rm count$ 就可以做到 $\sqrt n$ 了。 ```cpp ll n ; ll res ; ll ans ; #define gcd __gcd ll sum(ll x){ return (x - (x / 5) - (x >> 1) + (x / 10)) ; } ll all_2_5(ll x){ ll ret = 0 ; ll re2 = log(x) / log(2) + 1 ; ll re5 = log(x) / log(5) + 1 ; ll sum2 = 1 ; ll sum5 ; for (int i = 0 ; i <= re2 ; ++ i){ sum5 = 1 ; for (int j = 0 ; j <= re5 ; ++ j){ if (sum5 * sum2 > x) break ; sum5 = 5ll * sum5 ; ++ ret ; } sum2 = sum2 * 2ll ; } return ret ; } int main(){ cin >> n ; if (n <= 10000000){ for (int i = 1 ; i <= n ; ++ i){ int j = i, o ; while (j % 2 == 0) j /= 2 ; while (j % 5 == 0) j /= 5 ; // while (j % 10 == 0) j /= 10, re10 *= 10 ; //cout << re2 << " " << re5 << " " << re10 << '\n' ; // cout << j << '\n' ; ans += n / j ; // cout << ans << '\n' ; } } else { // cout << all_2_5(10) << '\n' ; for (ll l = 1, r ; l <= n ; l = r + 1){ r = n / (n / l) ; ans += (sum(r) - sum(l - 1)) * 1ll * (n / l) * all_2_5(n / l) ; } } cout << ans << '\n' ; return 0 ; } ```