[蓝桥杯 2024 国 Java B] 美丽区间

问题描述

美丽区间是这样的一组区间：[L1,R1]、[L2,R2]、[L3,R3].. 构造美丽区间需要满足以下条件：

1. L1=1
2. Li≤Ri
3. Ri−Li≥K
4. 对于任意的 i>1，有 Li=Ri−1  +1
5. gcd(Li,Ri)=1，其中 gcd指两个数的最大公约数
6. 在满足上述条件的情况下，Li、Ri​ 之间的差尽可能的小。

输入格式

第一行输入一个整数 K。 第二行输入一个整数 T，表示有 T 组测试用例。 接下来 T 行，每行输入一个整数 n。

输出格式

对每个输入的整数 n，输出一行，包含一个整数，表示 n 属于第几个美丽区间。

样例输入

10
3
123
33
10

样例输出

11
3
1

样例说明

第 1 个美丽区间为：[1,11]。

第 2 个美丽区间为：[12,23]。

第 3 个美丽区间为：[24,35]。

⋯⋯

第 11 个美丽区间为：[120,131]。

评测用例规模与约定

对于 60% 的评测用例：1≤T≤10^3，1≤K≤10^6，1≤n≤10^6。

对于 100% 的评测用例：1≤T≤10^6，1≤K≤10^6，1≤n≤10^6。

解题思路

要找出输入的整数在第几个区间，因为我们可以先根据题目要求把所有的美丽区间找到，并存储好美丽区间的左边界以及该区间属于第几个区间。

为了方便我们后续进行查找，我们可以用TreeMap存储这些数据，key存储左边界，value存储第几区间。

因为 TreeMap内部已经封装了基于红黑树的高效查找逻辑，并提供了一系列方法直接支持范围查询、上下界查找等操作。可以直接使用floorEntry()方法查找<=n的最大键值对，再用getValue()取值就能得到属于第几个区间。

代码

import java.util.Scanner;
import java.util.TreeMap;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int k=sc.nextInt();//key存储区间左边界，value存储属于第几个区间TreeMap<Integer, Integer> map=new TreeMap<>();int l=1;int cnt=1;map.put(l,cnt);//存储第一个区间l=k+2;//从第二个区间开始cnt=2;while(l<=1000000) {int r=l+k;while(gcd(l,r)!=1) {r++;}map.put(l, cnt);l=r+1;cnt++;}int t=sc.nextInt();while(t-->0) {int n=sc.nextInt();//查找<=n的最大键值对，再取值int res=map.floorEntry(n).getValue();System.out.println(res);}sc.close();}private static int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}}