1 介绍

本博客用来记录筛质数、分解质因数和快速幂相关的题目。

2 训练

题目1：1292哥德巴赫猜想

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>using namespace std;const int N = 1e6 + 10;set<int> s;//处理出N以内的所有奇质数
void init() {vector<bool> st(N, false);vector<int> primes;for (int i = 2; i < N; ++i) {if (!st[i]) primes.emplace_back(i);for (int j = 0; primes[j] <= N / i; ++j) {st[primes[j] * i] = true;if (i % primes[j] == 0) break; }}for (auto x : primes) {if (x % 2 == 1) s.insert(x);}return;
}int main() {init();for (auto it = s.begin(); ; it++) {int x = *it;//cout << "x = " << x << endl;if (distance(s.begin(), it) > 5) break;}int x;while (cin >> x, x) {auto iter = s.lower_bound(x);bool flag = true;while (true) {int a = *iter;//cout << a << endl;int b = x - a;if (s.count(b)) {printf("%d = %d + %d\n", x, b, a);flag = false;break;}if (iter == s.begin()) break;iter--;}if (flag) {printf("Goldbach's conjecture is wrong.");}}return 0;
}

题目2：1293夏洛克和他的女朋友

C++代码如下，