题解：P12254 [蓝桥杯 2024 国 Java B] 美丽区间

· · 题解

题目意思已经很详细，这里不在复述。

思路

由于 n 的范围很大，如果每次询问都 O(n) 查找就是 O(tn) 的复杂度，肯定是不能过的，所以考虑预处理。

先设一个 a 数组，用于存储答案。

然后，设置两个数组，l 和 r，含义与题目相同。

接着，按照题目来模拟 5 个特征。

更多细节见代码。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int cnt[5000010],l[5000010],r[5000010],k,t,n,top = 1;
signed main(){
    scanf("%lld",&k);
    while (true){
        l[top] = r[top - 1] + 1,r[top] = l[top] + k;
        while (__gcd(l[top],r[top]) != 1) r[top]++;
        for (int i = l[top];i <= r[top];i++) cnt[i] = top;
        if (r[top] >= 1000000) break;
        top++;
    }
    scanf("%lld",&t);
    while(t--) scanf("%lld",&n),printf("%lld\n",cnt[n]);
}