「欧拉计划」部分简单题目题解

Project Euler | 欧拉计划

Project Euler | 欧拉计划 是一系列需要利用数学和计算机知识及技巧来解答的问题

题面

#1. Multiples of 3 and 5

Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

3的倍数和5的倍数

如果我们列出10以内所有3或5的倍数,我们将得到3、5、6和9,这些数的和是23。

求1000以内所有3或5的倍数的和。

#2. Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

斐波那契数列中的每一项都是前两项的和。由1和2开始生成的斐波那契数列前10项为:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 考虑该斐波那契数列中不超过四百万的项,求其中为偶数的项之和。

#3. Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

最大质因数

13195的所有质因数为5、7、13和29。

600851475143最大的质因数是多少?

#4. Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

最大回文乘积

回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。

找出由两个3位数相乘得到的最大回文乘积。

#5. Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

最小倍数

2520是最小的能够被1到10整除的数。

最小的能够被1到20整除的正数是多少?

题解

#1. Multiples of 3 and 5

简单容斥一下就可以 O(1) 做了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>

#define int long long

int n;

int calc (int x) {
int cnt = n / x;
return x * cnt * (cnt + 1) >> 1;
}

signed main () {
scanf("%lld", &n); --n;
printf("%lld\n", calc(3) + calc(5) - calc(3 * 5));
}

#2. Even Fibonacci numbers

没管那么多...直接打了个暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>

#define int long long

const int MAXN = 1000000 + 10;
const int limit = 4000000;

int f[MAXN];
int ans = 2;

signed main () {
f[1] = 1; f[2] = 2;
ans = 2;
for (int i = 3; f[i - 1] + f[i - 2] <= limit; i++) f[i] = f[i - 1] + f[i - 2], ans += (f[i] & 1) ? 0 : f[i];
printf("%lld\n", ans);
}

3. Largest prime factor

直接分解质因数就没了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>

#define int long long

int split_max (int x) {
int ret = 1;
for (int i = 2; i * i <= x; i++) {
if (x % i) continue;
ret = i;
while (x % i == 0) x = x / i;
}
if (x > 1) ret = x;
return ret;
}

signed main () {
int n;
scanf("%lld", &n);
printf("%lld\n", split_max(n));
return 0;
}

#4. Largest palindrome product

直接暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>

const int MAXN = 100;

int s[MAXN];

bool check (int x) {
int siz = 0;
while (x >= 10) {
s[++siz] = x % 10;
x = x / 10;
}
if (x) s[++siz] = x;
for (int i = 1; i <= siz >> 1; i++) {
if (s[i] != s[siz - i + 1]) return false;
}
return true;
}

int main () {
int n;
scanf("%d", &n);

int max = 0;
for (int i = 1; i < n; i++)
for (int j = 1; j < n; j++)
if (check(i * j) && i * j > max) max = i * j;

printf("%d\n", max);
}

#5. Smallest multiple

对每个数分解, 指数取 max, 大概是 \text O(n\sqrt n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

std::unordered_map <int, int> cnt;
std::vector <int> p;

long long pow (long long base, int p) {
long long ret = 1;
while (p) {
if (p & 1) ret = ret * base;
base = base * base; p = p >> 1;
}
return ret;
}

void split (int x) {
for (int i = 2; i * i <= x; i++) {
if (x % i) continue;
if (!cnt.count(i)) p.push_back(i);
int tot = 0;
while (x % i == 0) x = x / i, tot++;
cnt[i] = std::max(tot, cnt[i]);
}
if (x > 1) {
if (!cnt.count(x)) p.push_back(x);
cnt[x] = std::max(1, cnt[x]);
}
}

int main () {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) split(i);
long long ans = 1;
for (auto i : p) ans = ans * pow(i, cnt[i]);
printf("%lld\n", ans);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!