题目：
我没有记忆化的 TLE70 代码：
#include<math.h>
#include<iostream>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
I AK IOI;
typedef long long ll;
ll n,m,ans,L,R;
void dfs(ll x,ll step){
if(step==10)return;
ll i=n/x+1;
if(i>=L&&i<=R)ans=max(ans,n%i);
if(i!=0)dfs(n/i+1,step+1);
if(i>1)dfs(n/(i-1)+1,step+1);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
ll maxn=n/2+1,mmod=n%maxn;
while(m--){
cin>>L>>R;
if(L<=maxn&&maxn<=R)cout<<mmod<<endl;
else if(L>maxn)cout<<n-L<<endl;
else{
ans=max(n%L,n%R);
ll i1=n/L+1;
if(i1>=L&&i1<=R)ans=max(ans,n%i1);
ll i2=n/R+1;
if(i2>=L&&i2<=R)ans=max(ans,n%i2);
ll kl=n/L;
if(kl!=0)dfs(kl,0);
ll kr=n/R;
if(kr!=0)dfs(kr,0);
cout<<ans<<endl;
}
}
return 0;
}
这是我改成记忆化以后的 WA30 的代码：
#include<math.h>
#include<iostream>
#include<unordered_map>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
I AK IOI;
typedef long long ll;
ll n,m,ans,L,R;
unordered_map<ll,ll>mem;
ll dfs(ll x,ll step){
if(mem.count(x))return mem[x];
if(step==10)return ans;
ll i=n/x+1;
if(i>=L&&i<=R)ans=max(ans,n%i);
if(i!=0)ans=max(ans,dfs(n/i+1,step+1));
if(i>1)ans=max(ans,dfs(n/(i-1)+1,step+1));
return mem[x]=ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
ll maxn=n/2+1,mmod=n%maxn;
while(m--){
cin>>L>>R;
if(L<=maxn&&maxn<=R)cout<<mmod<<endl;
else if(L>maxn)cout<<n-L<<endl;
else{
mem.clear();
ans=max(n%L,n%R);
ll l1=0,l2=0;
ll i1=n/L+1;
if(i1>=L&&i1<=R)ans=max(ans,n%i1);
ll i2=n/R+1;
if(i2>=L&&i2<=R)ans=max(ans,n%i2);
ll kl=n/L;
if(kl!=0)ans=max(ans,dfs(kl,0));
ll kr=n/R;
if(kr!=0)ans=max(ans,dfs(kr,0));
cout<<ans<<endl;
}
}
return 0;
}
实在找不出哪里有问题了 qwq