P6583 回首过去

EAlivn · 2021-06-28 18:30:20 · 题解

解析问题

若(\dfrac{x}{y})是十进制有限小数, 则 (\dfrac{y}{gcd(x,y)}) 的质因子只有 2 和 5.

枚举 i,j,d , 表示 y=2^i5^j*d , 则 x 的数量为 ⌊(\dfrac{n}{d})⌋ , 可以数论分块.

枚举 d 的时候, 需要满足 d 不能整除 2 或 5 , 所以数论分块的时候要容斥一下.

因为每 10 个数中必定有 6 个数是 2 或 5 的倍数, 所以数论分块的时候先处理整十的部分, 对于剩下的暴力枚举一下即可.

#include<bits/stdc++.h>
using namespace std;
long long q[40000],cnt,tmp;
bool cmp(long long x,long long y) {
    return x>y;
}
inline long long read() {
    long long x;
    scanf("%lld",&x);
    return x;
}
int main() {
    long long n=read();
    long long t1=0,t2=1,t3=t1,t4=3,t5=t4;
    while(t2<=n) {
        t5=1;
        while(t2*t5<=n){
            q[++cnt]=t2*t5;
            long long tmp=5;
            t5*=tmp;
        }
        long long tmp=2;
        t2*=tmp;
    }
    long long sum=0;
    q[0]=n+1;
    sort(q+1,q+1+cnt,cmp);
   long long ans=0;
    for(int p=1; p<=cnt; p++) {
        for(long long i=n/q[p-1]+1,j; i<=n/q[p]; i=j+1) {
            j=min(n/q[p],n/(n/i));
            long long k=(j-i+1)/10,num=4*k;
            for(k=i+k*10; k<=j; k++)
                if(k%2&&k%5) num++;
            sum+=num*(n/i);
        }
        ans+=sum;
    }
    printf("%lld\n",ans);
    return 0;
}

这是我的第一篇题解,求通过!