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 分可以这么写

        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 了。


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 ;
}