A11289 | Weird LCM Operations
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Given an integer $n$ , you construct an array $a$ of $n$ integers, where $a_i = i$ for all integers $i$ in the range $[1, n]$ . An operation on this array is defined as follows:
- Select three distinct indices $i$ , $j$ , and $k$ from the array, and let $x = a_i$ , $y = a_j$ , and $z = a_k$ .
- Update the array as follows: $a_i = \operatorname{lcm}(y, z)$ , $a_j = \operatorname{lcm}(x, z)$ , and $a_k = \operatorname{lcm}(x, y)$ , where $\operatorname{lcm}$ represents the least common multiple.
Your task is to provide a possible sequence of operations, containing at most $\lfloor \frac{n}{6} \rfloor + 5$ operations such that after executing these operations, if you create a set containing the greatest common divisors (GCDs) of all subsequences with a size greater than $1$ , then all numbers from $1$ to $n$ should be present in this set.After all the operations $a_i \le 10^{18}$ should hold for all $1 \le i \le n$ .
We can show that an answer always exists.
- Select three distinct indices $i$ , $j$ , and $k$ from the array, and let $x = a_i$ , $y = a_j$ , and $z = a_k$ .
- Update the array as follows: $a_i = \operatorname{lcm}(y, z)$ , $a_j = \operatorname{lcm}(x, z)$ , and $a_k = \operatorname{lcm}(x, y)$ , where $\operatorname{lcm}$ represents the least common multiple.
Your task is to provide a possible sequence of operations, containing at most $\lfloor \frac{n}{6} \rfloor + 5$ operations such that after executing these operations, if you create a set containing the greatest common divisors (GCDs) of all subsequences with a size greater than $1$ , then all numbers from $1$ to $n$ should be present in this set.After all the operations $a_i \le 10^{18}$ should hold for all $1 \le i \le n$ .
We can show that an answer always exists.
输入格式
The first line contains one integer $t$ ( $1 \le t \le 10^2$ ) — the number of test cases. The description of the test cases follows.
The first and only line of each test case contains an integer $n$ ( $3 \leq n \leq 3 \cdot 10^{4}$ ) — the length of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^{4}$ .
The first and only line of each test case contains an integer $n$ ( $3 \leq n \leq 3 \cdot 10^{4}$ ) — the length of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^{4}$ .
输出格式
The first line should contain an integer $k$ ( $0 \leq k \leq \lfloor \frac{n}{6} \rfloor + 5$ ) — where $k$ is the number of operations.
The next $k$ lines should contain the description of each operation i.e. $3$ integers $i$ , $j$ and $k$ , where $1 \leq i, j, k \leq n$ and all must be distinct.
The next $k$ lines should contain the description of each operation i.e. $3$ integers $i$ , $j$ and $k$ , where $1 \leq i, j, k \leq n$ and all must be distinct.
输入输出样例
输入 #1
3 3 4 7
输出 #1
1 1 2 3 1 1 3 4 3 3 5 7 5 6 7 2 3 4
In the third test case, $a = [1, 2, 3, 4, 5, 6, 7]$ .
First operation:
$i = 3$ , $j = 5$ , $k = 7$
$x = 3$ , $y = 5$ , $z = 7$ .
$a = [1, 2, \operatorname{lcm}(y,z), 4, \operatorname{lcm}(x,z), 6, \operatorname{lcm}(x,y)]$ = $[1, 2, \color{red}{35}, 4, \color{red}{21}, 6, \color{red}{15}]$ .
Second operation:
$i = 5$ , $j = 6$ , $k = 7$
$x = 21$ , $y = 6$ , $z = 15$ .
$a = [1, 2, 35, 4, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y)]$ = $[1, 2, 35, 4, \color{red}{30}, \color{red}{105}, \color{red}{42}]$ .
Third operation:
$i = 2$ , $j = 3$ , $k = 4$
$x = 2$ , $y = 35$ , $z = 4$ .
$a = [1, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y), 30, 105, 42]$ = $[1, \color{red}{140}, \color{red}{4}, \color{red}{70}, 30, 105, 42]$ .
Subsequences whose GCD equal to $i$ is as follows:
$\gcd(a_1, a_2) = \gcd(1, 140) = 1$
$\gcd(a_3, a_4) = \gcd(4, 70) = 2$
$\gcd(a_5, a_6, a_7) = \gcd(30, 105, 42) = 3$
$\gcd(a_2, a_3) = \gcd(140, 4) = 4$
$\gcd(a_2, a_4, a_5, a_6) = \gcd(140, 70, 30, 105) = 5$
$\gcd(a_5, a_7) = \gcd(30, 42) = 6$
$\gcd(a_2, a_4, a_6, a_7) = \gcd(140, 70, 105, 42) = 7$
First operation:
$i = 3$ , $j = 5$ , $k = 7$
$x = 3$ , $y = 5$ , $z = 7$ .
$a = [1, 2, \operatorname{lcm}(y,z), 4, \operatorname{lcm}(x,z), 6, \operatorname{lcm}(x,y)]$ = $[1, 2, \color{red}{35}, 4, \color{red}{21}, 6, \color{red}{15}]$ .
Second operation:
$i = 5$ , $j = 6$ , $k = 7$
$x = 21$ , $y = 6$ , $z = 15$ .
$a = [1, 2, 35, 4, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y)]$ = $[1, 2, 35, 4, \color{red}{30}, \color{red}{105}, \color{red}{42}]$ .
Third operation:
$i = 2$ , $j = 3$ , $k = 4$
$x = 2$ , $y = 35$ , $z = 4$ .
$a = [1, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y), 30, 105, 42]$ = $[1, \color{red}{140}, \color{red}{4}, \color{red}{70}, 30, 105, 42]$ .
Subsequences whose GCD equal to $i$ is as follows:
$\gcd(a_1, a_2) = \gcd(1, 140) = 1$
$\gcd(a_3, a_4) = \gcd(4, 70) = 2$
$\gcd(a_5, a_6, a_7) = \gcd(30, 105, 42) = 3$
$\gcd(a_2, a_3) = \gcd(140, 4) = 4$
$\gcd(a_2, a_4, a_5, a_6) = \gcd(140, 70, 30, 105) = 5$
$\gcd(a_5, a_7) = \gcd(30, 42) = 6$
$\gcd(a_2, a_4, a_6, a_7) = \gcd(140, 70, 105, 42) = 7$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted