题解：CF2044E Insane Problem

· · 题解

题解：CF2044E Insane Problem

分析

我们先将 \frac{y}{x}=k^n 转化为 x=\frac{y}{k^n}。

题目说了 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9，也就是说 1 \leq x, y \leq 10^9。那么我们算一下， 当 k 取 \mathtt2 时，n 最大约为 30。我们可以枚举 n，算出当前 x 的取值区间以及 y 的取值区间，再将两个区间的交集累加入答案中。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int k,l1,r1,l2,r2,sum=0,asd=1;
        cin>>k>>l1>>r1>>l2>>r2;
        for(int i=0;r2/asd>=l1;i++){
            int num=max(0,min(r1,r2/asd)-max(l1,(l2-1)/asd+1)+1);
            asd*=k,sum+=num;
        }
        cout<<sum<<"\n";
    }
    return 0;
}