B

算法 1

可以发现判定 $\frac pq$ 是否合法的过程相当于每次把大数减掉两倍的小数，问是否能保持全正然后变成 $(1,0)$。暴力实现判断，时间复杂度 $O(nm(n+m))$，期望得分 $10$。

注意到过程相当于欧几里得算法求 $\gcd$，可以变成 $O(nm\log nm)$，或者加个记忆化变成 $O(nm)$，期望得分 $35$。

算法 2

$n=1$ 时只有 $m$ 是偶数合法。$n=2$ 时只有 $m=4k+1$ 合法，$n=3$ 时不合法，$n=4$ 时 $m=8k+1$ 合法。期望得分 $5\sim 20$。结合算法 1 期望得分 $55$。

算法 3

观察大样例发现答案不大，考虑从 $(0,1)$ 开始搜索答案。如果你像笔者一样加个 map 或者 umap 判重，时间复杂度 $O(ans\log ans)$，但是 umap 里存 $O(ans)$ 个元素就爆了，大概可以通过 $n,m\le 10^5$，期望得分 $65$。

注意到搜索出来的所有东西必然满足互质，而且两两不同，因为每一对合法数 $(p,q)$ 倒着做的过程是唯一的，所以正着做也不会算重，把 umap 撇了，就是 $O(ans)$，据实现获得 $90\sim 100$ 分。如果实在跑不过 $100$ 可以在最后特判一下：如果现在搜到的 $p,q$ 满足 $p\le m<q\le n$，且 $q$ 正在加 $2p$，可以把后面的部分用除法算出来，可以快一点点。

算法 4

上面这个还是很难过 $3\cdot 10^7$。骗你的，我也不会做。原题。