@Klein_Moretti @HuanL 卡完常以后加了搜索深度还是WA70？
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define int long long
#define R register
I AK IOI;
namespace fastIO{char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
inline void read(string&s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
inline void write(const string&s){for(R int i=0;i<(int)s.size();i++){putchar(s[i]);}}
inline void write(const char&c){putchar(c);}
}using namespace fastIO;
int n,m,ans,L,R1;
unordered_map<int,unordered_map<int,int> >mem;
inline int dfs(const int &x,const int &step){
if(step==11) return ans;
if(mem[x].count(step))return mem[x][step];
int i=n/x+1;
int cur=ans;
if(i>=L&&i<=R1)cur=max(cur,n%i);
if(i!=0)cur=max(cur,dfs(n/i+1,step+1));
if(i>1)cur=max(cur,dfs(n/(i-1)+1,step+1));
mem[x][step]=cur;
return cur;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
read(n);
read(m);
int maxn=n/2+1,mmod=n%maxn;
while(m--){
read(L);
read(R1);
if(L<=maxn&&maxn<=R1){
write(mmod);
putchar('\n');
}
else if(L>maxn){
write(n-L);
putchar('\n');
}
else{
mem.clear();
ans=max(n%L,n%R1);
int l1=0,l2=0;
int i1=n/L+1;
if(i1>=L&&i1<=R1)ans=max(ans,n%i1);
int i2=n/R1+1;
if(i2>=L&&i2<=R1)ans=max(ans,n%i2);
int kl=n/L;
if(kl!=0)ans=max(ans,dfs(kl,0));
int kr=n/R1;
if(kr!=0)ans=max(ans,dfs(kr,0));
write(ans);
putchar('\n');
}
}
i_ak ioi;
}