P6583回首过去

P6538回首过去

题意：
求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le n$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。

• Subtask 1（40 分），$1 \le n \le 10^3$；
• Subtask 2（40 分），$1 \le n \le 10^7$；
• Subtask 3（20 分），$1 \le n \le 10^{12}$。
  思路：
  10进制小数必然可以写成 $\frac{a}{1000…}$ 的形式，即分母为 $10^{x}$ ,即 $2^{x} \cdot 5^{x}$

  做法一

  枚举x,y为 $N^2$,约分gcd为 $logN$,判断分母 $logN$
  复杂度：$O(N^2logN)$

  做法二

  把分数分解可以写成以下形式: $ \frac{bc}{ac} $
  其中a只含2和5的因子，c为不包含2和5的因子，b的范围为 $[1,\lfloor \frac{n}{c} \rfloor]$
  a可以预处理出来，枚举a值，再枚举c值，每次加上 $\lfloor \frac{n}{c} \rfloor$(即b的个数)，分母[1,n]都被枚举了一遍
  复杂度： $O(N)$

  做法三

  发现答案会加上很多个 $ \lfloor \frac{n}{c} \rfloor $,考虑整除分块 性质： $a \cdot c$ 最大值范围限定为n,即随着c的增大，a的最大值会减小
  此时先枚举c的值，这样b还是 $[1, \lfloor \frac{n}{c} \rfloor ]$的任意数，a限定在 $[1, \lfloor \frac{n}{c} \rfloor ]$范围内，因此可以每次减少a的最大值使其小于 $\lfloor \frac{n}{c} \rfloor$,可以用一个数来维护a能满足的个数,c的范围内不能被2和5整除的个数可以利用类似前缀和的方法算出
  定义 $g(l,r,x)$ 表示l,r内被x整除的个数
  则c的个数为 $g(l,r,1)-g(l,r,2)-g(l,r,5)+g(l,r,10)$
  每次将答案进行累加即可
  复杂度： $O(\sqrt{N})$

  signed main(){
    cin.tie(0)->sync_with_stdio(0);
    ll n;
    vector<ll> a;
    cin>>n;
    for(ll i=1;i<=n;i*=2){
        for(ll j=i;j<=n;j*=5)a.push_back(j);
    }
    sort(a.begin(),a.end());
    int cnt=a.size()-1;
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1){
        ll x=n/l;
        //r=(x==0?n:n/x);
        r=n/x;
        while(cnt&&a[cnt]>x)cnt--;
        ll v=r-l+1;
        v-=r/2-(l-1)/2;
        v-=r/5-(l-1)/5;
        v+=r/10-(l-1)/10;
        ans+=v*(cnt+1)*x;
    }
    cout<<ans<<"\n";
    return 0;
  }