Ｃ++的位运算

作者为蒟蒻高中牲，若有不妥之处请多多包含，并望于评论区指正，不胜感激！

目录：

• Ｃ++的位运算

Ｃ++中有6种位运算符：

• &: 与

  1 & 1 = 1

  1 & 0 = 0

  0 & 0 = 0

• |: 或

  1 | 1 = 1

  1 | 0 = 1

  0 | 0 = 0

• ~: 非

  ~ 1 = 0

  ~ 0 = 1

• ^: 异或

  1 ^ 1 = 1

  1 ^ 0 = 0

  0 ^ 0 = 1

• <<: 左移

  $1 << 1 = 10_２$

  $1 << 2 = 100_2$

• >>: 右移

  $11_2 >> 1 = 110_2$

题目传送门

目录：

• 题目传送门
  • 题目解读
  • 说明/提示
  • AC 代码

这是一道我弟拿给我做题目，本来想着普及−应该挺简单的，结果翻车了

题目解读

本题要求我们找出给定区间内的所有“回文质数”¹。我一看就想着：先筛质数，再判断是不是回文数~~，结果大意失荆州——开了一个占用4G内存的prime[100000000]~~于是我终于注意到了题目中的提示：

说明/提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为 5 的回文数：

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
    for (d2 = 0; d2 <= 9; d2++) {
        for (d3 = 0; d3 <= 9; d3++) {
          palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
        }
    }
}

于是我便把提示里的代码复制了几份～

AC 代码

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

// 判断一个数是否为质数
bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

vector<int> palindromes;

int main() {
    int st, ed;
    scanf("%d%d", &st, &ed);
    
    // 生成所有可能的回文数
    
    // 1位回文数
    for (int i = 1; i <= 9; i++) {
        palindromes.push_back(i);
    }
    // 偶数位回文数(除了11)都能被11整除，不是回文数
    // 2位回文数
    palindromes.push_back(11);
    
    // 3位回文数
    for (int i = 1; i <= 9; i += 2) { // 只考虑奇数开头，偶数开头的必不是质数
        for (int j = 0; j <= 9; j++) {
            palindromes.push_back(i * 101 + j * 10); // iji形式
        }
    }
    
    // 5位回文数
    for (int i = 1; i <= 9; i += 2) { 
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                palindromes.push_back(i * 10001 + j * 1010 + k * 100); // ijkji形式
            }
        }
    }
    
    // 7位回文数
    for (int i = 1; i <= 9; i += 2) { 
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                for (int l = 0; l <= 9; l++) {
                    palindromes.push_back(i * 1000001 + j * 100010 + k * 10100 + l * 1000); // ijklkji形式
                }
            }
        }
    }
    
    // 9位回文数（虽然超出了1亿，但为了完整性）
    for (int i = 1; i <= 9; i += 2) { 
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                for (int l = 0; l <= 9; l++) {
                    for (int m = 0; m <= 9; m++) {
                        int palindrome = i * 100000001 + j * 10000010 + k * 1000100 + l * 100010 + m * 10000;
                        if (palindrome <= 100000000) { // 只添加不超过1亿的
                            palindromes.push_back(palindrome);
                        }
                    }
                }
            }
        }
    }
    
    // 排序
    sort(palindromes.begin(), palindromes.end());
    
    // 遍历回文数数组，找出其中的质数并输出
    for (int palindrome : palindromes) {
        if (palindrome > ed) break;
        if (palindrome >= st && isPrime(palindrome)) {
            printf("%d\n", palindrome);
        }
    }
    
    return 0;
}

Over!