题解：AT_pakencamp_2023_day3_d GCD

Xu_Chenxi · 2026-07-23 18:55:29 · 题解

思路

我们发现需要让所有区间的最大公因数都不相同，所以我们可以想到令一个序列中的每一个数都等于 2 的正整数次幂，此时一个区间的最大公因数就由该区间内幂次最低的数决定。

但是我们发现若一个区间内的幂次单调递增，那么区间 (i,j) 和区间 (i,j+1) 的最大公因数都是 a_i，因此我们考虑让每一个区间内幂次最低的数均不同。很容易想到的一点是，若选择两个质数 m 与 n，令 m 的幂次递增，n 的幂次递减，此时区间 (i,j) 中 m 的幂次最低的数为 a_i，n 的幂次最低的数即为 a_j，此时该区间的最大公因数由左右端点共同决定。

所以，为方便计算，我们可以令 a_i = 2^i \times 3^{31-i}，此时每一个区间的最大公因数是唯一确定的。

代码

#include<bits/stdc++.h>
using namespace std;
unsigned long long x=1;
unsigned long long y=1;
int main()
{
    for (int i=1;i<=30;i++)
        y=y*3;
    for (int i=1;i<=30;i++)
    {
        cout<<x*y<<" ";
        x=x*2;
        y=y/3;
    }
}