Codeforces Round #701 (Div. 2) D. Multiples and Power Differences

題意

給定 n ? m n*m n?m的矩陣 A A A，要求構造出一個 n ? m n*m n?m的矩陣 B B B，滿足

• 1 ≤ b i , j ≤ 1 0 6 1\le b_{i,j}\le 10^6 1≤bi,j?≤106

• b i , j b_{i,j} bi,j?是 a i , j a_{i,j} ai,j?的倍數

• 矩陣 B B B中每個元素與相鄰任何元素的值之差的絕對值必須是某個正整數的四次方

限制

1 ≤ n , m ≤ 500 1\le n,m\le 500 1≤n,m≤500

1 ≤ a i , j ≤ 16 1\le a_{i,j}\le 16 1≤ai,j?≤16

思路

注意到 1 ≤ a i , j ≤ 16 1\le a_{i,j}\le 16 1≤ai,j?≤16，首先想到的是應當先求出一個數 d d d，且 1 1 1到 16 16 16任一數字都是 d d d的因子

16 ! 16! 16!顯然過大，所以 d = l c m { 1 , 2 , ? ? , 16 } = 720720 < 1 0 6 d=lcm\{1,2,\cdots ,16\}=720720\lt 10^6 d=lcm{1,2,?,16}=720720<106

然后可以假設 B B B矩陣所有元素都是 d d d，但題目要求的是相鄰差值為某個正整數的四次方

所以可以錯位令其加上 A A A矩陣中數的四次方，使得：

對于任意一個值為 d d d的位置，它與四周元素的差值為四周元素值的四次方

對于任意一個值不為 d d d的位置，它的四周元素值均為 d d d（差值即自身的四次方）

代碼

#include<bits/stdc++.h>
using namespace std;

const int d=2*2*2*2*3*3*5*7*11*13; //lcm(1~16)

int main()
{
    int n,m,a;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a);
            if((i+j)&1)
                printf("%d",d);
            else
                printf("%d",d+a*a*a*a);
            putchar(j==m?'\n':' ');
        }
    return 0;
}

To cnblogs