当前位置 博文首页 > ApocalypseTq的博客：P6583 回首过去 题解
2333333333
考虑首先合法的答案一定是分数约分后分母的质因数只有?2,52,5。也就是说
\frac{x}{y}=\frac{\frac{x}{\gcd(x,y)}}{2^p5^q}yx?=2p5qgcd(x,y)x??
其中?p,qp,q?都是极大的。稍微化一下可以发现
y=\gcd(x,y)\times 2^p5^qy=gcd(x,y)×2p5q
那么就可以对每一个?yy?求有多少个?xx?是合法的。考虑?xx?一定可以写作?d\times \gcd(x,y)d×gcd(x,y)，那么也就是说由于?\gcd(x,y)gcd(x,y)?固定(因为?2^p5^q2p5q?极大)要统计有多少个本质不同的?dd?，因为?xx?只能在?[1,n]\cap \mathbb {Z_+}[1,n]∩Z+??中取值，所以不难发现一共有?\left\lfloor\dfrac{n}{\gcd(x,y)}\right\rfloor?gcd(x,y)n???种取法。所以?8080?分可以这么写
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)i=1∑n??ζ(i)n??(1)
其中?\zeta(i)ζ(i)?是最大的不含质因子?2,52,5?的?ii?的因子。考虑调换枚举顺序，枚举?\zeta(i)ζ(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)(1)=k=1∑n??kn??×[2?k]×[5?k]×count(?kn??)
其中最后一个?\rm count(t)count(t)?表示?1\sim t1～t?之间有多少只包含?2,52,5?作为质因数的数。原因很简单，因为我们枚举的是?\zeta(i)ζ(i)，\zeta(i)ζ(i)?需要搭配上?2^p5^q2p5q?才会有效，所以计数有多少?\leq n≤n?的数包含?kk?就是相当于计数有多少?\leq \left\lfloor\dfrac{n}{k}\right\rfloor≤?kn???的数包含?2^p5^q2p5q。于是这么做就是?O(\sqrt n\log ^2 n)O(n?log2n)?的了。稍微预处理一下?\rm countcount?就可以做到?\sqrt nn??了。
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 ;
}