[ECL-Final 2017D]Mr. Panda and Geometric Sequence

Link

Solution

x划分出的前三项为a[1],a[2],a[3],则a[1]a[2]a[3]=a[2]^3\le x\le 10^{15}a[2]\le 10^5

Code

std::vector<long long> nums;
void Prep() {
    const int N=1e5;
    const long long UP=1e15;
    //k*p*q
    auto Join=[](long long a,long long b)->long long {
        for(long long x=b;x;x/=10)
            if((a*=10)>UP)
                return UP+1;
        return a+=b;
    };

    for(long long p=1;p<=N;++p)
        for(long long q=p+1;p*q<=N;++q)
            if(std::__gcd(p,q)==1) {
                for(long long k=1;k*p*q<=N;++k) {
                    long long x=Join(Join(k*p*p,k*p*q),k*q*q),a=k*q*q;
                    while(x<=UP) {
                        nums.push_back(x);
                        if(a*q%p)
                            break;
                        else
                            x=Join(x,a=a*q/p);
                    }
                }
            }
    std::sort(nums.begin(),nums.end());
    nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
}

int main() {
    Prep();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long l,r;fin>>l>>r;
        auto Solve=[&](long long x) {
            return std::upper_bound(nums.begin(),nums.end(),x)-nums.begin();
        };

        fout<<Solve(r)-Solve(l-1)<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注