codeforces 476D Dreamoon and Sets（数学）_codeforces dreamoon

作者：IT小白 | 2024-02-10 21:13:45

踩

codeforces dreamoon

Dreamoon likes to play with sets, integers and $\text{[math]}$ . $\text{[math]}$ is defined as the largest positive integer that divides both a and b.

Let S be a set of exactly four distinct integers greater than 0. Define S to be of rank k if and only if for all pairs of distinct elements si, sjfrom S, $\text{[math]}$ .

Given k and n, Dreamoon wants to make up n sets of rank k using integers from 1 to m such that no integer is used in two different sets (of course you can leave some integers without use). Calculate the minimum m that makes it possible and print one possible solution.

Input

The single line of the input contains two space separated integers n, k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ 100).

Output

On the first line print a single integer — the minimal possible m.

On each of the next n lines print four space separated integers representing the i-th set.

Neither the order of the sets nor the order of integers within a set is important. If there are multiple possible solutions with minimal m, print any one of them.

   Sample test(s) 
 
     input 
   
1 1

     output 
   
5
1 2 3 5

     input 
   
2 2

     output 
   
22
2 4 6 22
14 18 10 16

Note

For the first example it's easy to see that set {1, 2, 3, 4} isn't a valid set of rank 1 since $\text{[math]}$

题意：给一个N，K。要找N个集合，每个集合有四个不同的数字，每个数字只能在一个集合。要让每个集合满足以下条件：

集合中任意两个数字的gcd（最大公约数）为K。

现在要让N个集合中最大的数字最小，并输出方案。

当K==1的时候，我们要让集合中的每个数两两互质。

当K！=1的时候，我们将K==1的时候的方案的每个数乘以K，就是答案。

所以我们只要解决K==1的情况即可。换句话说，问题就是找n个集合，每个集合中数两两互质，并且一个数只属于一个集合。要让N个集合中最大的数最小。

假设我们已知前N个集合的最大的数为x，那么对于第N+1个集合来说，我们就是要从x+1开始找，找四个互质的数，并且最大的数最小。

假设x+1为奇数，我们发现：x+1，x+2，x+3，x+5，这四个数一定能构成一个集合。

假设x+1为偶数，我们发现若x+1必选，最优情况下4个数为：x+1，x+2，x+4, x+6。

显然当x+1为偶数的时候，不选x+1，选x+2一定更优。当x+1为奇数的时候，选x+1显然最优。

初始的时候x=0。我们可以预处理出n个集合中的数。复杂度O（n）。

代码如下：


#include<stdio.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#define inff 0x3fffffff
#define eps 1e-8
#define nn 210000
#define mod 1000000007
typedef long long LL;
const LL inf64=LL(inff)*inff;
using namespace std;
LL a[11000][6];
int n,k;
void init()
{
    int i,j;
    LL id=1;
    for(i=1;i<=10000;i++)
    {
        for(j=1;j<=3;j++)
        {
            a[i][j]=id++;
        }
        a[i][4]=++id;
        id+=2;
    }
}
int main()
{
    int i,j;
    init();
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        printf("%I64d\n",a[n][4]*(LL)k);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=4;j++)
            {
                printf("%I64d%c",a[i][j]*k,j==4?'\n':' ');
            }
        }
    }
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/75464