大家对于 PE 题目有啥疑问或者回答别人的疑问也可以在这个评论区进行哦。
001 ~ 100
Problem 1: Multiples of 3 or 5 / 3 或 5 的倍数
直接枚举即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
int sum = 0; for(int i = 1;i < 1000;i++) {
if(i % 3 == 0 || i % 5 == 0) sum += i;
} cout << sum << endl;
return 0;
}注意是 $<1000$，不是 $\le1000$。
Problem 2: Even Fibonacci numbers / 偶斐波那契数
同样枚举即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
int a = 1, b = 1, c = 0, sum = 0;
while(c <= 4000000) {
c = a + b; a = b; b = c;
if(c % 2 == 0) sum += c;
} cout << sum << endl;
return 0;
}Problem 3: Largest prime factor / 最大质因数
可以直接 $O(\sqrt n)$ 枚举因子。注意 $num$ 最后可能是个大质数。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long num = 600851475143; long long ans = 0;
for(long long i = 2;i * i <= num;i++) {
if(num % i == 0) {
num /= i, ans = max(ans, i);
}
} cout << max(ans, num) << endl;
return 0;
}Problem 4: Largest palindrome product / 最大回文乘积
直接枚举两个数。可以使用 to_string 函数将数转成字符串。
#include <bits/stdc++.h>
using namespace std;
int main() {
int ans = 0;
for(int i = 100;i <= 999;i++) {
for(int j = 100;j <= 999;j++) {
string s = to_string(i * j);
string t = s; reverse(t.begin(), t.end());
if(s == t) ans = max(ans, i * j);
}
} cout << ans << endl;
return 0;
}Problem 5: Smallest multiple / 最小公倍数
就是求 $\displaystyle\operatorname{lcm}\limits_{i=1}^{20}i$。那么可以使用 C++ 自带的（从 C++17 开始支持）gcd 函数。
#include <bits/stdc++.h>
using namespace std;
int lcm(int a, int b) { return a * b / gcd(a, b); }
int main() {
long long ans = 1; for(int i = 1;i <= 20;i++) ans = lcm(ans, i);
cout << ans << endl;
return 0;
}Problem 6: Sum square difference / 平方和与和平方之差
枚举。注意不一定第一个比第二个大，要取绝对值。
#include <bits/stdc++.h>
using namespace std;
int main() {
int sum1 = 0, sum2 = 0;
for(int i = 1;i <= 100;i++) sum1 += i * i, sum2 += i;
cout << abs(sum1 - sum2 * sum2) << endl;
return 0;
}Problem 7: 10001st prime / 第 10001 个质数
猜一波小的质数不会太大，于是直接枚举。
#include <bits/stdc++.h>
using namespace std;
bool isprime(int x) {
for(int i = 2;i * i <= x;i++) {
if(x % i == 0) return false;
} return true;
} int main() {
int cnt = 0; for(int i = 2;;i++)
if(isprime(i) && ++cnt == 10001) return cout << i, 0;
return 0;
}Problem 8: Largest product in a series / 连续数字最大乘积
直接枚举。
#include <bits/stdc++.h>
using namespace std;
string s = " 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
int main() {
long long mx = 0;
for(int i = 1;i <= 988;i++) {
long long p = 1; for(int j = i;j <= i+12;j++) p *= (s[j] - '0');
mx = max(mx, p);
} cout << mx << endl;
return 0;
}Problem 9: Special Pythagorean triplet / 特殊毕达哥拉斯三元组
可以枚举 $a,b$，然后算出 $c$ 后再判断。
#include <bits/stdc++.h>
using namespace std;
int main() {
for(int a = 1;a <= 1000;a++) {
for(int b = 1;b <= 1000;b++) {
if((a + b) >= 1000) break;
if(a * a + b * b == (1000 - a - b) * (1000 - a - b)) {
cout << a * b * (1000 - a - b) << endl;
}
}
}
return 0;
}Problem 10: Summation of primes / 质数求和
看起来如果 $n=2000000$ 时，$O(n\sqrt n)$ 会超时，但是实际上远远跑不满，所以直接枚举。记得开 long long。
#include <bits/stdc++.h>
using namespace std;
int isp(int x) {
for(int i = 2;i * i <= x;i++) {
if(x % i == 0) return false;
} return true;
} int main() { long long ans = 0;
for(int i = 2;i <= 2000000;i++) {
if(isp(i)) ans += i;
} cout << ans << endl;
return 0;
}Problem 11: Largest product in a grid / 方阵中的最大乘积
这个方阵不太方便直接弄到程序里，所以当做输入数据就可以了。
#include<iostream>
using namespace std;
int num[30][30], ans;
int dirx[4] = {-1, 0, 1, 1};
int diry[4] = {1, 1, 1, 0};
int main() {
for (int i = 5; i < 25; i++) {
for (int j = 5; j < 25; j++) {
cin >> num[i][j];
}
}
for (int i = 5; i < 25; i++) {
for (int j = 5; j < 25; j++) {
for (int k = 0; k < 4; k++) {
int t = num[i][j];
for (int l = 1; l < 4; l++) {
int x = i + dirx[k] * l;
int y = j + diry[k] * l;
t *= num[x][y];
}
ans = max(ans , t);
}
}
}
cout << ans << endl;
return 0;
}Problem 12: Highly divisible triangular number / 有很多约数的三角形数
直接枚举直接枚举直接枚举。怎么前面的题都是无脑题啊？
#include <bits/stdc++.h>
using namespace std;
bool fac(long long x) {
int num = 0; for(long long i = 1;i * i <= x;i++) {
if(x % i == 0) num += 2;
if(i * i == x) num--;
} return num >= 500;
} int main() {
long long ans = 1; while(!fac((ans + 1) * ans / 2)) ans++;
cout << (ans + 1) * ans / 2 << endl;
return 0;
}Problem 13: Large sum / 大和
直接写一个高精度，或者用 Python 即可。
我写的是高精度，代码比较长，题目很简单，就不贴了。
101 ~ 200
前面题有点水，从 $101$ 开始好了。
Problem 101: Optimum polynomial / 最优多项式
上难度。考虑先将 $u_1 \sim u_{10}$ 算出来，然后直接对着每个 $u_1 \sim u_i$ 拉插一下就可以得到题目中所说的“最优多项式” 了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 101;
int x[N], y[N];
int quick_pow(int sum,int k) {
int ret = 1; while(k) {
if(k & 1) ret = ret * sum; k >>= 1; sum = sum * sum;
} return ret;
} int Lagerange(int k,int sum) {
int ret = 0;
for(int i = 1;i <= k;i++) {
int now = y[i];
int sum1 = 1, sum2 = 1;
for(int j = 1;j <= k;j++) {
if(i == j)continue;
sum1 *= sum - x[j];
sum2 *= x[i] - x[j];
}
ret += now * sum1 / sum2;
}
return ret;
} signed main() {
for(int i = 1;i <= 11;i++) {
x[i] = i; int cur = 1; y[i] = 1;
for(int j = 1;j <= 10;j++) {
cur = -cur;
y[i] += cur * quick_pow(x[i],j);
}
} int ans = 1; for(int i = 2;i <= 10;i++) {
ans += Lagerange(i,i+1);
} cout << ans << endl; return 0;
}
鄂公网安备 42010202000505 号