Submission #40528631

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN=1010;
ll n,m,q,a[MAXN],b[MAXN],lca;

ll calc(ll x,int mode=0){
	ll L=1,R=n,t=0,lt=0,rt=0;
	while(1){
		ll M=(L*a[t%m] + R*b[t%m]) / (a[t%m] + b[t%m]);
		if(M==x)break;
		if(M>x)R=M-1,rt+=(t>=lca);else L=M+1,lt+=(t>=lca);
		t++;
	}
	return (mode==0) * t + (mode==1) * lt + (mode==2) * rt;
}
ll calc2(ll x,ll y){
	ll L=1,R=n,t=0;
	while(1){
		ll M=(L*a[t%m] + R*b[t%m]) / (a[t%m] + b[t%m]);
		if(M==x || M==y)break;
		if((M>x) != (M>y))break;
		t++;
		if(M>x)R=M-1;else L=M+1;
	}

	return t;
}

void solve(ll L,ll R){
	lca=calc2(L,R);
	ll val=calc(L) + calc(R) - 2*lca;

	ll ans=2*(R-L+calc(L,1)+calc(R,2));

	ans-=val;
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(false);

	cin>>n>>m;
	rep(i,0,m-1)cin>>a[i]>>b[i];
	cin>>q;
	rep(i,1,q){
		ll L,R;cin>>L>>R;
		solve(L,R);
	}


    return 0;
}

Submission Info

Judge Result