去年讲的题到今年还不会做，wtcl
对于无序数对 ((x, y))，每次可进行 ((x,y) o (x, y mod x)) 的操作，定义 (F(x,y)) 表示将无序数对 ((x, y)) 操作到出现 0 的最小步数。当给定 (n,m) 时，定义 (mn = MIN {F(x,y) },1 le xle n, 1 le y le m,cnt = sum_{i=1}^n sum_{j=1}^m [F(x,y)=mn])。共 (3 imes 10^5) 组询问，每次给定 (n,m)，求 (mn, cnt)。
我们可以构造一种 (F(x,y)) 最大的 ((x, y))，显然当 (x,y) 为斐波那契数列的相邻两项的时候 (F(x,y)) 会比较大（考虑反推，尽量让 (x,y) 小一些）。于是我们可以直接在斐波那契数列上二分找到合法的最大的 (F(x,y))，作为 (mn) 输出。
现在的问题在于求 (cnt)。考虑到 (sum_{i=1}^n sum_{j=1}^m [F(x,y)=k]) 可能会有很多，但是很多是类似的，比如 (F(2,3),F(2,5),F(2,7),F(2,9),...) 都可以归为一类：((2,3+2t))。于是我们考虑用最小的这样的数对来计算所有的合法数对。方便起见，我们只考虑 (i le j) 的 ((i, j)) 数对，并规定“步数为 (k) 的类”为符合 (F(i,j)=k,i < j le 2i) 的所有数对。那么，我们可以打表求出步数为 (k) 的“类”都有什么：
发现 (k) 类恰好有 (k) 个数对。并且发现第 (k) 类第 (i) 个数对恰好是第 (k-1) 类第 (i) 个数对的“反推”，最后一个可以由第 (k - 1) 类第 (1) 个数对转化来： ((i,j) o (i+j,2i+j))。于是直接预处理出所有“类”，每次 (O(log)) 回答询问。
注意不要爆 long long。
关键代码：
inline void work() {
ll n, m, res = 0; read(n), read(m);
if (n > m) swap(n, m);
if (n == 1) {
printf("1 %lld
", m % P);
return ;
}
int p;
p = upper_bound(f + 1, f + 1 + ftot, n) - f - 1;
if (f[p + 1] > m) --p;
printf("%d ", p);
if (p == 1) res = n % P;
for (int i = 1; i <= p; ++i)
if (pr[p][i].first <= n && pr[p][i].second <= m)
res = (res + (m - pr[p][i].second) / pr[p][i].first + 1) % P;
swap(n, m);
for (int i = 1; i <= p; ++i)
if (pr[p][i].first <= n && pr[p][i].second <= m)
res = (res + (m - pr[p][i].second) / pr[p][i].first + 1) % P;
printf("%lld
", (res % P + P) % P);
}
int main() {
f[0] = f[1] = 1;
for (int i = 2; f[i - 1] <= 3e18; ++i) f[i] = f[i - 1] + f[i - 2], ftot = i;
pr[1][1] = MP(1, 2);
for (int i = 2; i <= 91; ++i) {
for (int j = 1; j < i; ++j) pr[i][j] = MP(pr[i - 1][j].second, pr[i - 1][j].first + pr[i - 1][j].second);
ll a = pr[i - 1][1].first, b = pr[i - 1][1].second;
pr[i][i] = MP(a + b, a + a + b);
for (int j = 1; j <= i; ++j) {
if (pr[i][j].first > 2e18) pr[i][j].first = 2e18;
if (pr[i][j].second > 2e18) pr[i][j].second = 2e18;
}
}
}