B3738 [信息与未来 2018] 素数方阵题解

· · 题解

B3738 [信息与未来 2018] 素数方阵

题目描述已经很简洁，这里就不再重复了。

思路讲解

这题就是蛇形方阵和素数判断（筛）的结合，先讲蛇形方阵： 按照题目模拟，像向右移动，如果越界或者这个地方已经有数了，就向下……按照右、下、左、上的顺序，分别写一个循环就行了。

Code:

while (k <= n * n){
    while(y < n && !a[x][y + 1]){
        a[x][++y] = ans[k++];
    }
    while(x < n && !a[x + 1][y]){
        a[++x][y] = ans[k++];
    }
    while(y > 1 && !a[x][y - 1]){
        a[x][--y] = ans[k++];
    }
    while(x > 1 && !a[x - 1][y]){
        a[--x][y] = ans[k++];
    }
}

接下来是素数：我们可以用一个埃氏筛来进行处理： 众所周知，一个质数的倍数一定是合数。

所以假如我吗遍历到了一个质数，（设这个质数为 p）就把区间 [1,n] 中所有 p 的倍数筛去。

至于为什么这样能筛去所有的合数呢，因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。

让我们进一步的优化：

  1. 我们会先筛 2 的所有倍数，然后筛 3 的所有倍数，但筛除 3 的倍数时，我们还是从 3 的 2 倍开始筛，其实 3 \times 2 ，已经被 2 \times 3时筛过了。又比如说筛 5 的倍数时，我们从 5 的 2 倍开始筛，但是 5 \times 2会先被 2 \times 5 筛去, 5 \times 3会先被 3 \times 5 会筛去，5 \times 4会先被 2 \times 10 筛去，所以我们每一次只需要从 i ^ {2} 开始筛，因为 (2，3,\dots,i - 1) 倍已经被筛过了。

  2. 另外，判断一个数 n 是不是质数，我们只判断 [2, \sqrt{n} ] 内有没有它的因子。在筛合数的时候，我们也可以这样做，因为一个合数的最小质因子一定小于等 \sqrt{n}。所以对于区间 [1,10 ^ {7}]，最大的合数是 10 ^ {7}, 它的最小质因子一定是小于等于 \sqrt{10 ^ {7}}，区间内其他的合数的最小质因子也一定是小于等于 \sqrt{10 ^ {7}} 的，所以只需要用 [1, \sqrt{10 ^ {7}}] 中的质数就可以筛去[1, 1 0 ^ {7}]中所有的合数。

Code(优化后的埃氏筛):

bool isPrime[100000005];
void is_prime(int n){
    isPrime[1] = 1;  
    for(int i = 2;i <= n / i;i++){ 
        if(isPrime[i] == 0) {
            for(int j = i * i;j <= n;j += i){
                isPrime[j] = 1;   
            }
        }
    }
}

时间复杂度近似 O(n)。由于 n \le 20，所以我们的函数中的 n 只要开到 400 就够了（作者为了保险，开了 10000）。

有一点不同，我们还需要额外开一个数组（这里是 ans）记录每一个素数。最终代码如下：

void is_prime(int n){
    isPrime[1] = 1;  
    for(int i = 2;i <= n;i++){ 
        if(isPrime[i] == 0) {
            ans[++f] = i;
            for(int j = i * i;j <= n;j += i){
                isPrime[j] = 1;   
            }
        }
    }
}

整体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 20;
int a[maxn + 5][maxn + 5],ans[100005];
int n,k = 1,x = 1,y,f,cx,cy;
bool isPrime[1000005];
void is_prime(int n){
    isPrime[1] = 1;  
    for(int i = 2;i <= n;i++){ 
        if(isPrime[i] == 0) {
            ans[++f] = i;
            for(int j = i * i;j <= n;j += i){
                isPrime[j] = 1;   
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> cx >> cy;
    is_prime(10000);
    while (k <= n * n){
        while(y < n && !a[x][y + 1]){
            a[x][++y] = ans[k++];
        }
        while(x < n && !a[x + 1][y]){
            a[++x][y] = ans[k++];
        }
        while(y > 1 && !a[x][y - 1]){
            a[x][--y] = ans[k++];
        }
        while(x > 1 && !a[x - 1][y]){
            a[--x][y] = ans[k++];
        }
    }
    cout << a[cx][cy] << endl;  
    return 0;
}

提交记录。

求赞，谢谢。