#P10497. [2021年联测]很大
[2021年联测]很大
题目描述
一个矩阵的元素两两不同,有 行、 列,按行连续存放在内存中。原矩阵第 行第 列的元素放在内存第 个位置,下标从 开始。
要在原内存中完成矩阵转置,应把该元素移到第 个位置。一次操作可以交换任意两个内存位置的元素。求完成转置至少需要多少次交换。
输入格式
输入包含若干行,读到文件末尾为止。每行两个整数 ,表示一次询问。
输出格式
对每次询问输出一行一个整数,表示所需最少交换次数对 取模的结果。
样例
1 1
1 2
762395 50914
1
4
994178060
的矩阵只需交换第 和第 个元素的位置。 的矩阵需要四次交换。
数据范围
为非负整数,,询问次数不超过 。时间限制 秒,空间限制 MB。
| 子任务 | 分值 | 额外限制 | 询问次数上界 |
|---|---|---|---|
| 1 | 3 | 或 | |
| 2 | 20 | 240 | |
| 3 | 17 | ||
| 4 | 30 | 1 | |
| 5 |