Submission #5826386

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define dmp(x) cerr<<#x<<":"<<x<<endl
typedef pair<int,int> P;
typedef pair<int,P> PP; 
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1e9+7;

signed main(){
  int n,q;
  cin>>n>>q;
  for(int i=0;i<q;i++){
    int v,w;
    cin>>v>>w;
    if(n==1){
	 cout<<min(v,w)<<endl;
	 continue;
    }
    vector<int> vv,wv;
    while(v>1){
	 vv.pb(v);
	 v=(v+n-2)/n;
    }
    while(w>1){
	 wv.pb(w);
	 w=(w+n-2)/n;
    }
    sort(all(vv));
    sort(all(wv));
    int ans=1;
    for(int j=0;j<sz(vv)&&j<sz(wv);j++){
	 if(vv[j]!=wv[j])break;
	 ans=vv[j];
    }
    cout<<ans<<endl;
  }
  return 0;
}

Submission Info

Judge Result