2023杭电多校第三场 1012.Noblesse Code

传送门:Vjudge

前题提要:一道挺有意思的数论题.赛时对于这道题没什么想法,但是赛后细品之后其实感觉也就那么一回事.但是这种 更相损减术与辗转相除法 相转化的题目还是有点典的,需要好好消化一下.

首先看完题目.我们需要考虑的是$(A,B)$与$(a,b)$的相互转化关系.其中转化方法是使用类似于更相损减术的方法.显然.我们是不能直接转化的,因为对于更相损减术来说,如果$(A,B)$两个数相差太大,那么需要的复杂度就会爆炸.所以我们得考虑一种更有效率的方法.

因为是更相损减术,所以我们联想到它的好兄弟,辗转相除法.辗转相除法可以很好的解决更相损减术过程中不断的单向减少的过程(也就是不断的变为$(a,b-a)$).但是使用辗转相除法处理我们的$(A,B)$的话,显然会丢失中间的一些数对.就比如$(9,3)$,我们使用辗转相除法,进行一次就会得到$(0,3)$,此时我们会丢失中途本来可以得到的$(6,3),(3,3)$等数对,并且这些数对都是符合题意的,那么我们该怎么解决这种问题呢.

考虑我们的辗转相除法是解决更相损减术固定一个值,另一个值不断减少的过程,所以在这过程中我们舍掉的这些数对必然是一个端点和我们的初始端点相同,另一个端点成等差数列分布.也就是上述中的$9,6,3,0$.并且我们需要知道的是,假设我们对初始的$(A,B)$进行更相损减术操作,我们后面得到的数对都是一一对应的,也就是$(A,B)$得到$(a,b)$我们的$(a,b)$就能通过题面中的操作重新变成$(A,B)$.所以此时考虑我们需要解决的问题,假设我们的$(ai,bi)$能通过题面中的操作变成(A,B),我们的$(ai,bi)$必然处于我们的$(A,B)$的变化链中.

那么我们可以考虑记录对$(A,B)$的辗转相除法的过程,也就是记录每一次辗转相除法之后的数.如果我们将数看做节点,那么我们相对于更相损减术省略掉的那些点就在我们的两两节点相连的链上.更一般的,我们可以将整个过程看成一棵树.那么对于所有的(A,B)树来说,就是一颗森林.那么对于我们的$(ai,bi)$来说,假设这个数对刚好是(A,B)树中的一个节点.那么显然的我们的$(ai,bi)$可以变为$(A,B)$.如果不是节点的话,那么我们需要将$(ai,bi)$进行一次辗转相除法操作,因为这样我们就可以将(ai,bi)转化成一个森林上的一个节点(原因是显然的,因为我们森林中的一个节点必然是一次辗转相除法之后的结果),那么对于此时新的$(a,b)$,我们就知道假设我们的$旧(a,b)$能转化成$(A,B)$,意味着我们的$(A,B)$在我们的$(a,b)$这个节点的上面(此处的上面是指(A,B)能转化成新(a,b),并且(A,B)能转化成旧(a,b)).又因为对于在同一条链上的点来说,我们是很容易知道哪一个数固定,哪一个数成等差的(比一下大小即可).所以对于我们的合法的$(A,B)$与$(a,b)$来说,(A,B)中成等差的那一个数必然比$(a,b)$中要大.(此处我们可以使用二分).

其实到这里我们的$trick$基本上就详细的讲完了.接下来讲讲具体做法(仅供参考)

乍一看对于每一节点似乎都是一个二叉树,但是仔细看发现一个简单的性质.假设我们的节点为$(a,b)$,我们此时$a<b$的话,那么对于某个在它上面的$(A,B)$来说,我们此时必然是有$A>B$的,反之则($B>A$).原因考虑辗转相除法的性质,此处不在赘述.同样的,我们发现不可能存在一个节点$(a=b)$.(这里的点是指辗转相除法过程中的节点,而不是之前所说的$(ai,bi)$)
考虑使用$vector$来记录每一个节点的点对以及它的成等差的数的端点.就比如$(9,6)$,我们进行一次操作得到$(3,6)$,我们记录点对$(3,6)$,并且将$9$存到$vector$中,这意味着假设我们之后的$(ai.bi)$是$(3,6)$的话,我们的$9$比$6$大,所以可以转化.那么对于一个点对来说,我们可能有很多个$(A,B)$可以到达它,此时,我们需要存下每一个端点,然后在$(ai,bi)$的时候直接用二分来查找有一个满足端点大于即可.

这里还有一个小细节需要注意,那就是当我们的$(ai,bi)$中$ai=bi$时,我们此时转化方法并不是单向的,而是双向的.也就是一个点处于两条链中.所以此时我们需要同时加上$(ai,0),(0,bi)$的结果.除此之外,根据辗转相除法的性质,其他点必不能同时处于两条链上.(因为既要$a>=b,b>=a$那么只能相等)

---

下面是具体的代码部分(前文已足够详尽,代码不再补充注释):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
map<pair<int,int>,vector<int>>tree;
void build(int a,int b) {if(a==0||b==0) return ;if(a<=b) {tree[make_pair(a,b%a)].push_back(b);build(a,b%a);}else {tree[make_pair(a%b,b)].push_back(a);build(a%b,b);}
}
signed main() {int T=read();while(T--) {tree.clear();int n=read();int q=read();for(int i=1;i<=n;i++) {int A=read();int B=read();build(A,B);}for(auto &it:tree) {sort(it.second.begin(),it.second.end());}for(int i=1;i<=q;i++) {int a=read();int b=read();if(a==b) {cout<<tree[make_pair(a,0)].size()+tree[make_pair(0,b)].size()<<endl;}else if(a<b) {pair<int,int>last_node=make_pair(a,b%a);auto pos=lower_bound(tree[last_node].begin(),tree[last_node].end(),b);cout<<tree[last_node].end()-pos<<endl;}else {pair<int,int>last_node=make_pair(a%b,b);auto pos=lower_bound(tree[last_node].begin(),tree[last_node].end(),a);cout<<tree[last_node].end()-pos<<endl;}}}return 0;
}