题解 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;
}