#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>

#define int long long

using namespace std;

int f(int x){
    return x-((int)(x/2)+(int)(x/5)-(int)(x/10));
}

int S(int n,int k){
    int ans=0;
    for(int l=1,r,t;l<=n;l=r+1){
        if(k/l)r=min(k/(k/l),n);
        else r=n;
        ans+=(k/l)*(f(r)-f(l-1));
    }
    return ans;
}

int N;

signed main(void){

    cin>>N;
    int ans=0,y=1,z=1;
    while(y<=N){
        z=1;
        while(z<=N)ans+=S(N/z/y,N),z<<=1;
        y*=5;
    }
    cout<<ans<<endl;

    return 0;
}

复杂度是常数很小的 $O(\sqrt{n}\log^2n)$

大致做法是枚举分母和分子分母的 $\gcd$，也就是一个这样的东西：

然后 TLE 死了

但是这个大概只有 5e8 级别啊。。为啥会 TLE 啊