Zeros Everywhere#13100

Zeros Everywhere (Çözgüdiň düşündirişi)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

First of all , swap the order of summation and fix the base $y$ first , base $1$ contributes nothing so

x = 1 \sum n y = 1 \sum n f_{y} (x) = y = 2 \sum n Z_{y}, Z_{y} = x = 1 \sum n f_{y} (x)

\sum_{x=1}^{n}\sum_{y=1}^{n} f_y(x)=\sum_{y=2}^{n} Z_y \quad , \quad Z_y=\sum_{x=1}^{n} f_y(x)

Now instead of counting zeros number by number , let's count them position by position. Fix a position $p \geq 0$ p \ge 0 with place value $w = y^{p}$ w=y^p. A zero there must not be a leading zero , so some higher digit of $x$ is non-zero , i.e. $⌊ \frac{x}{w y} ⌋ \geq 1$ \left\lfloor \frac{x}{wy} \right\rfloor \ge 1 , thus every such $x$ is of the form

x = h \cdot w y + 0 \cdot w + l, h \geq 1, 0 \leq l < w

x=h\cdot wy+0\cdot w+l \quad , \quad h \ge 1 \ , \ 0 \le l < w

For a fixed $h$ these are exactly the $w$ consecutive integers $[h \cdot w y, h \cdot w y + w - 1]$ [h\cdot wy , h\cdot wy+w-1] , let $H = ⌊ \frac{n}{w y} ⌋$ H=\left\lfloor \frac{n}{wy} \right\rfloor :

$1 \leq h < H$ 1 \le h < H : the whole block fits below $n$ , so $w$ numbers each.
$h = H$ h=H : the block is cut by $n$ , so $min (w, (n mod w y) + 1)$ \min(w,(n \bmod wy)+1) numbers.
$h > H$ h > H : nothing.

So position $p$ contributes

(H - 1) \cdot w + min (w, (n mod w y) + 1)

(H-1)\cdot w+\min(w,(n \bmod wy)+1)

and it exists only while $w y \leq n$ wy \le n.

Notice for $y > n$ y > \sqrt{n} only $p = 0$ p=0 exists , so the inner loop runs once , and for $y \leq n$ y \le \sqrt{n} it runs $lo g_{y} n$ \log_y n times , thus the total work is $O (n)$ .

Complexity $O (n)$ .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    ll n;cin>>n;
    ll ans=0;
    for(ll y=2;y<=n;y++){
        for(ll w=1;w*y<=n;w*=y){
            ll H=n/(w*y);
            ans+=(H-1)*w+min(w,n%(w*y)+1);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}