区间最大值（挖了无数次）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

长度为 n 的数组 a，下标从1开始，定义 a[i]=n%ia[i]=n % ia[i]=n%i

有 m链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
//@@zhihuijiazeng@@@要知道 n mod i = n -[n/i] *i,但是 n/i 只有 2*sqrt(n)个不同的取值。于是，每个 n/i 的值，要使 n mod i 最大，那 i 就应该尽量小。建议去学一学数论分块的方法，这个题用数论分块的方法就可以一遍过。

第一行两个正整数 n, m

接下来 m 行，每行两个正整数 L, R

n≤1e8n leq 1e8n≤1e8，m≤1e4m leq 1e4m≤1e4，1≤L≤R≤n1 leq L leq R leq n1≤L≤R≤n

输出 m 行，每行一个整数表示询问结果

示例1

复制7 3 1 1 1 4 5 6

7 3
1 1
1 4
5 6

复制0 3 2

0
3
2

组询问 {L,R}，求 maxi=LRa[i]max_{i=L}^{R} a[i]maxi=LR​a[i]

//@@@@@

#include 
#include 
using namespace std;
int n,m;
int main(){
	cin>>n>>m;
	int i;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		for(i=2;n/i+1>b;i++);
		if(a<(n/i+1))
		{
			cout< 

 // 虽然是写了个题解，但是写的人也不一定会很明白其中的微妙。