# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

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

posted on 2020-06-02 20:13:33 | under 题解 |

2333333333

$$\frac{x}{y}=\frac{\frac{x}{\gcd(x,y)}}{2^p5^q}$$

$$y=\gcd(x,y)\times 2^p5^q$$

        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)$$

$$(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)$$


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