题解：CF2044E Insane Problem

· · 题解

题意很清楚，这里不再阐述，这是一道推公式的题目。

思路

由题意，

\frac{y}{x}=k^n

两边同时乘 x 再除以 k^n

\frac{y}{k^n}=x

由于 l_2 \le y \le r_2 ，所以

\frac{l_2}{k^n} \le x \le \frac{r_2}{k^n}

那么很简单，枚举 n ，求出上不等式与 l_1 \le x \le r_1 的交集之和，但是代码里需要对 \frac{l_2}{k^n} 和 \frac{r_2}{k^n} 进行上取整和下取整。

什么？你问我交集怎么求？设两不等式 l_1 \le x \le r_1 和 l_2 \le x \le r_2 求他们的交集很简单，就是 \max(\min (r_1,r_2) - \max(l_1,l_2), 0) 。

那代码就很简单了，但是注意细节。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, k, l1, r1, l2, r2;
int main(){
    cin >> T;
    while (T--){
        cin >> k >> l1 >> r1 >> l2 >> r2;
        ll sum = 0, ksm = 1ll;
        for (ll i = 0; r2 / ksm >= l1; i++) sum += max(0ll, min(r1, r2 / ksm) - max(l1, (l2 - 1ll) / ksm + 1) + 1ll), ksm *= k;
        cout << sum << endl;
    }
    return 0;
}