做手机网站要注意,wordpress主题首页文件夹,什么平台可以免费发广告,做设计必须知道的几个网站E. Weird LCM Operations#xff1a;
题目大意#xff1a; 思路解析#xff1a;
这是一道构造题#xff0c;那么观察这个构造有啥性质#xff0c;观察到最多操作次数为 n/6 5#xff0c;然后每次操作需要选择三个数#xff0c;如果每次操作的三个数都不和之前的重复的…E. Weird LCM Operations
题目大意 思路解析
这是一道构造题那么观察这个构造有啥性质观察到最多操作次数为 n/6 5然后每次操作需要选择三个数如果每次操作的三个数都不和之前的重复的话应该至少需要n/3次那么容易想到每次操作应该只需要操作后半部分且每次操作之间选择的数不重复。
证明为什么操作后半部分是正确的假设 n27可以发现 13和26本来gcd就是13了无论26选择哪些数反正一定会保留13这个因子则前半部分的gcd是天然满足的。
还可以发现当 选择 13 14 15这样的两个奇数一个偶数时一定会同时满足这三个的gcd。
一个奇数两个偶数不行。
三个奇数也可以但是发现一个偶数就需要两个奇数肯定不会有这么多额外的奇数所以这个性质似乎没什么用
三个偶数在这三个偶数都不含4这个因子时也可以满足这一下就很好的补充了在一直使用第一个性质后剩余的偶数过多带来的麻烦。
因为第四个性质要求每次需要使用不含4这个因子的偶数所以跨度为12则我们需要单独处理n小于14的情况然后其余情况利用第一个性质和第四个性质。 这两个性质的配合使用刚好可以组成一个循环
代码实现
import java.io.*;
import java.math.BigInteger;
import java.util.*;import static java.util.Collections.*;public class Main {public static void main(String[] args) throws IOException {int t f.nextInt();while (t 0) {solve();t--;}w.flush();w.close();br.close();}public static void solve() {int n f.nextInt();int[][][] pans new int[14][][];pans[3] new int[][]{{1, 2, 3}};pans[4] new int[][]{{1, 3, 4}};pans[5] new int[][]{{3, 4, 5}};pans[6] new int[][]{{1, 3, 5}, {2, 4, 6}};pans[7] new int[][]{{2, 4, 6}, {3, 5, 7}};pans[8] new int[][]{{2, 6, 8}, {3, 5, 7}};pans[9] new int[][]{{1, 3, 5}, {2, 4, 6}, {7, 8, 9}};pans[10] new int[][]{{3, 4, 5}, {2, 6, 8}, {7, 9, 10}};pans[11] new int[][]{{2, 6, 8}, {3, 5, 7}, {9, 10, 11}};pans[12] new int[][]{{1, 11, 12}, {6, 8, 10}, {5, 7, 9}};pans[13] new int[][]{{1, 13, 12}, {7, 9, 11}, {6, 8, 10}};if(n 14){w.println(pans[n].length);for (int i 0; i pans[n].length; i) {w.println(pans[n][i][0] pans[n][i][1] pans[n][i][2]);}}else {int[][] ans new int[n / 6 5][3];int res 0;int cur n;if ((n - 3) % 4 0){ans[0][0] 1; ans[0][1] 2; ans[0][2] n;res;cur --;}else if (n % 4 0){ans[0][0] 1; ans[0][1] n-1; ans[0][2] n;res;cur-2;}while (cur * 2 n){if (cur % 2 0){ans[res][0] cur; ans[res][1] cur - 4; ans[res][2] cur - 8;res;ans[res][0] cur - 3; ans[res][1] cur - 2; ans[res][2] cur - 1;res;ans[res][0] cur - 7; ans[res][1] cur - 6; ans[res][2] cur - 5;res;ans[res][0] cur - 11; ans[res][1] cur - 10; ans[res][2] cur - 9;res;}else {ans[res][0] cur - 2; ans[res][1] cur - 1; ans[res][2] cur;res;ans[res][0] cur - 6; ans[res][1] cur - 5; ans[res][2] cur - 4;res;ans[res][0] cur - 10; ans[res][1] cur - 9; ans[res][2] cur - 8;res;ans[res][0] cur - 11; ans[res][1] cur - 7; ans[res][2] cur - 3;res;}cur - 12;}w.println(res);for (int i 0; i res; i) {w.println(ans[i][0] ans[i][1] ans[i][2]);}}}static PrintWriter w new PrintWriter(new OutputStreamWriter(System.out));static Input f new Input(System.in);static BufferedReader br new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader new BufferedReader(new InputStreamReader(stream), 32768);tokenizer null;}public String next() {while (tokenizer null || !tokenizer.hasMoreTokens()) {try {tokenizer new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str null;try {str reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}
