题目背景
原题链接:https://oier.team/problems/X4D。
题目描述
对于一个正整数数对 (x,y),定义一次变换为:选择其中一个数 a,记另一个数为 b,同时选择一个正整数 k≤a,然后将 a 除以 k 向下取整,同时将 b 乘以 k。
形式化地说,对于数对 (x,y),你可以执行以下两种变换:
- 类型 1:取 1≤k≤x,令 (x,y)←(⌊kx⌋,y⋅k)。
- 类型 2:取 1≤k≤y,令 (x,y)←(x⋅k,⌊ky⌋)。
显然,变换后的数对仍然是正整数数对。
给出两组正整数数对 (a,b) 与 (c,d),你需要执行不超过 65 次变换将 (a,b) 变为 (c,d),或者报告无解。注意:你不需要最小化执行变换的次数。
需要注意数对是有序的,即若 x=y,则 (x,y)=(y,x)。
本题使用自定义校验器检验你的答案是否正确,因此若有多种满足条件的方案,你只需要输出任意一种。
输入格式
本题输入包含多组数据。
第一行,一个正整数 T,表示数据组数。对于每组数据:
- 仅一行,四个正整数 a,b,c,d,表示两组数对。
输出格式
对于每组数据:
- 若无解,
- 否则,
- 第一行,一个非负整数 m,表示你执行变换的次数。你需要保证 0≤m≤65,但不需要最小化 m。
- 接下来 m 行,第 i 行两个整数 op,k,表示你执行的第 i 次变换。其中 op∈{1,2} 表示变换类型,k 即为本次变换中选择的 k。
本题使用自定义校验器检验你的答案是否正确,因此若有多种满足条件的方案,你只需要输出任意一种。
提示
【样例解释】
对于第 1 组数据,不需要进行任何操作,因为初始时 a=c 且 b=d。
对于第 2 组数据,可以证明无解。
对于第 3 组数据,第一次变换后 (a,b)=(1,4),第二次变换后 (a,b)=(3,1),第三次变换后 (a,b)=(1,2)。
对于第 4 组数据,一次变换即可使 a=c 且 b=d。
对于第 5 组数据,可以证明无解。
对于第 6 组数据,第一次变换后 (a,b)=(26,129),第二次变换后 (a,b)=(52,64)。
对于第 7 组数据,第一次变换后 (a,b)=(31438,3878395026435),第二次变换后 (a,b)=(313814116,388538872)。
【数据范围】
本题采用捆绑测试。
令 n=max(a,b,c,d)。
子任务 |
n≤ |
特殊性质 |
分值 |
1 |
6 |
无 |
7 |
2 |
105 |
A |
11 |
3 |
C |
13 |
4 |
106 |
B |
23 |
5 |
109 |
C |
19 |
6 |
无 |
27 |
- 特殊性质 A:保证 ca=bd。
- 特殊性质 B:保证 a=b 且 c=d。
- 特殊性质 C:保证 a,b,c,d 在值域内独立均匀随机生成。
对于 100% 的数据,1≤T≤104,1≤a,b,c,d≤109。