【天猫座三重奏】

查看作者

打赏作者

当前位置：博科园 > 耀星科普协会 > 天文 > 正文

9

NASA

Lv.2普朗克长度

美国航天局（NASA）公布一张哈勃太空望远镜拍摄的「Arp 195」三重星系照片，中央的3个星系在引力作用下相互融合。这是一个位于北天星座天猫座的星系群，距离地球约7.63亿光年。该天体系统包含至少3个星系，宽度约20万光年，其中2个星系已经高度融合，第3个星系的恒星和气体因引力而向外延伸，形成一条长约20万光年的潮汐尾（Tidal tail）。摄影师：NASA

交互星系

哈勃望远镜

天文

恒星

探索

星系

科学

科普

NASA

Lv.2普朗克长度

星系间的碰撞不会因此而消亡，相反，他们会组成新的形状，并促进新的恒星形成，孕育出新的生命。

Kun

Lv.28蜂鸟

牛顿

在碰撞中重生

Tsyun

Lv.6十幺米空洞

阿基米德🌏

好美

神经蛙

Lv.1量子泡沫

壮观波澜之美

SKT-space

Lv.20 DNA

哈勃

郭巴拉

Lv.44猫眼星云

飞越太阳系

赠送了礼物[棒棒糖] $# 【MX-X4-T3】「Jason-1」数对变换 ## 题目描述对于一个**正整数**数对 $(x, y)$，定义一次变换为：选择其中一个数 $a$，记另一个数为 $b$，同时选择一个正整数 $k leq a$，然后将 $a$ 除以 $k$ 向下取整，同时将 $b$ 乘以 $k$。形式化地说，对于数对 $(x,y)$，你可以执行以下两种变换： – 类型 1：取 $1 le k le x$，令 $(x,y) gets (lfloor frac{x}{k} rfloor, y cdot k)$。 – 类型 2：取 $1 le k le y$，令 $(x,y) gets (x cdot k, lfloor frac{y}{k} rfloor)$。显然，变换后的数对仍然是正整数数对。给出两组正整数数对 $(a, b)$ 与 $(c, d)$，你需要执行**不超过 $bm{65}$ 次**变换将 $(a, b)$ 变为 $(c, d)$，或者报告无解。**注意：你不需要最小化执行变换的次数**。需要注意数对是有序的，即若 $x neq y$，则 $(x,y) neq (y,x)$。本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。 ## 输入格式 **本题输入包含多组数据。** 第一行，一个正整数 $T$，表示数据组数。对于每组数据： – 仅一行，四个正整数 $a, b, c, d$，表示两组数对。 ## 输出格式对于每组数据： – 若无解， – 仅一行一个字符串 `-1`。 – 否则， – 第一行，一个非负整数 $m$，表示你执行变换的次数。**你需要保证 $bm{0 le m le 65}$，但不需要最小化 $bm m$**。 – 接下来 $m$ 行，第 $i$ 行两个整数 $mathit{op}, k$，表示你执行的第 $i$ 次变换。其中 $mathit{op} in {1, 2}$ 表示变换类型，$k$ 即为本次变换中选择的 $k$。本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。 ## 样例 #1 ### 样例输入 #1 “` 7 1 1 1 1 1 2 1 1 2 2 1 2 10 10 2 50 5 5 4 10 80 43 52 64 987654321 123456789 313814116 388538872 “` ### 样例输出 #1 “` 0 -1 3 1 2 2 3 1 2 1 1 5 -1 2 1 3 2 2 2 1 31415 2 9982 “` ## 提示 **【样例解释】** 对于第 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)$。 | 子任务 | $nle$| 特殊性质 | 分值 | | :————–: | :—–: |:—–:| :——–: | | 1 | $6$ | 无 | $7$ | | 2 | $10^5$ | A | $11$ | | 3 | $10^5$ | C | $13$ | | 4 | $10^6$ | B | $23$ | | 5 | $10^9$ | C | $19$ | | 6 | $10^9$ | 无 | $27$ | – 特殊性质 A：保证 $dfrac{a}{c}=dfrac{d}{b}$。 – 特殊性质 B：保证 $a=b$ 且 $c=d$。 – 特殊性质 C：保证 $a,b,c,d$ 在值域内独立均匀随机生成。对于 $100%$ 的数据，$1 le T le 10^4$，$1 le a,b,c,d le 10^9$。用C++完成特殊性质 A和B$