CF476D Dreamoon and Sets解题报告

解题报告

CF476D Dreamoon and Sets解题报告：

更好的阅读体验

题意

给定$n,k$，构造$n$个元素互不相同的四元组，使得每个四元组的最大公约数为$k$。

求所有元素最大值最小的一组构造。

$1\leqslant n\leqslant 10000,1\leqslant k\leqslant 100$

分析

有点套路的MO题。

首先把所有四元组除以$k$，那么所有四元组的最大公约数为$1$。

考虑任意一个四元组都只能存在一个偶数，那么奇数起码三个，于是我们答案的下界为$6(n-1)+5=6n-1$。

构造一组方案达到下界：

由于$\gcd(a,b)=\gcd(a,b-a)$，我们贪心的让方案内的差尽可能小，于是我们直接把最近的三个奇数和一个偶数放在一个四元组内，即第$i(0\leqslant i<n)$组为$6i+1,6i+2,6i+3,6i+5$。

由$\gcd(a,b)=\gcd(a,b-a)$不难得知两两之间$\gcd$都为$1$，于是方案合法。

时间复杂度$O(n)$。

代码

#include<stdio.h>
int n,k;
int main(){
    scanf("%d%d",&n,&k);
    printf("%d\n",(6*n-1)*k);
    for(int i=0;i<n;i++)
        printf("%d %d %d %d\n",(6*i+1)*k,(6*i+2)*k,(6*i+3)*k,(6*i+5)*k);
    return 0;
}