zr模拟赛day8T2

正变换无法确定朝大还是朝小变换
考虑逆变换，因为逆变换只能是大减小
发现变成了辗转相减的形式
考虑优化成辗转相除
发现可以记录辗转相除中的每个关键点
记录成一个三元组
然后就发现可以二分查询了
有一个小细节是记录逆变换的时候要考虑是否为第一次变换

点击查看代码

#include<bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back 
#define p_b push_back
#define il inline
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define tri tuple<ll,ll,ll>
using namespace std;
const int N=1e5+1;
int n,q;
int m1,m2;
tri p1[N<<6],p2[N<<6];
signed main(){ios;cin>>n>>q;for(int i=1;i<=n;i++){ll x,y,f=0;cin>>x>>y;while(x&&y){if(x<=y){ll b=y%x;p1[++m1]={x,b,y-f},y%=x,f=1;}else{ll b=x%y;p2[++m2]={y,b,x-f},x%=y,f=1;}}}sort(p1+1,p1+m1+1);sort(p2+1,p2+m2+1);while(q--){ll x,y;cin>>x>>y;int ans=0;ans=upper_bound(p1+1,p1+m1+1,tri{x,y%x,1ll<<60})-p1;//保证前两位相等ans-=lower_bound(p1+1,p1+m1+1,tri{x,y%x,y})-p1;//至少从y开始ans=upper_bound(p2+1,p2+m2+1,tri{y,x%y,1ll<<60})-p2;ans-=lower_bound(p2+1,p2+m2+1,tri{y,x%y,x})-p2;cout<<ans<<'\n';}return 0;
}