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

上一篇: 「欧拉计划」部分简单题目题解

这一篇大概是 #6 #7 #9 #10 #12 #15 #73的题解

题面

#6. Sum square difference

The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640 .

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

#7. 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

#9. Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c , for which,

a^2 + b^2 = c^2

For example, 32 + 42 = 9 + 16 = 25 = 52 .

There exists exactly one Pythagorean triplet for which a + b + c = 1000 . Find the product abc .

#10. Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17

Find the sum of all the primes below two million.

#12. Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 . The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \cdots

Let us list the factors of the first seven triangle numbers:

1
2
3
4
5
6
7
 1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

#15. Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

#73. Counting fractions in a range

Consider the fraction, n\over d , where n and d are positive integers. If n<d and HCF(n,d)=1 , it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, [3/8, 2/5, 3/7], 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12\ 000 ?


题解

#6. Sum square difference

大概就这样:

image.png

题目就是求黑边的和

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
#define int long long
#define f(i, j) for (int i = 1; i <= j; i++)
signed main () {
int n, ans = 0;
scanf("%lld", &n);
f(i, n) f(j, n) ans += i == j ? 0 : i * j;
printf("%lld\n", ans);
return 0;
}

#7. 10001st prime

无话可说....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

#define int long long

const int N = 3000000;

int cnt;
int pri[N + 10];
bool vis[N + 10];

void pre () {
for (int i = 2; i <= N; i++) {
if (!vis[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= N; j++) vis[i * pri[j]] = 1;
}
}

signed main () {
pre();
printf("%lld\n", pri[10001]);
return 0;
}

#9. Special Pythagorean triplet

如果背过一些勾股数可能会比较容易...

如果数学直觉可能会直接反应过来是 ( 8 + 17 + 19 ) \times 25 = 1000

于是答案就是 25 ^ 3 \times (8 \times 17 \times 19)

Orz 但是我只会爆算

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
#define f(i, j) for (int i = 1; i <= j; i++)
int main () {
int n;
scanf("%d", &n);
f(i, n) f(j, i)
if (i * i + j * j == (n - i - j) * (n - i - j)) printf("%d = %d * %d * %d\n", i * j * (n - i - j), i, j, n - i - j);
return 0;
}

#10. Summation of primes

直接暴力

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
#include <bits/stdc++.h>

#define int long long

const int N = 3000000;

int cnt;
int pri[N + 10];
bool vis[N + 10];

void pre () {
for (int i = 2; i <= N; i++) {
if (!vis[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= N; j++) vis[i * pri[j]] = 1;
}
}

signed main () {
pre();
int ret = 0;
for (int i = 1; i <= cnt; i++)
if (pri[i] <= 2000000) ret += pri[i];
else break;
printf("%lld\n", ret);
return 0;
}

#12. Highly divisible triangular number

三角形数的公式 T _ n = {n \times (n + 1) \over 2}

注意到 n n + 1 是互质的, 于是分别计算两部分即可(根据奇数/偶数讨论)

这里放上暴力的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

#define int long long

int get (int x) {
int ret = 0, i;
for (i = 1; i * i <= x; i++) {
if (x % i) continue;
ret += 2;
}
if (i * i == x) ret--;
return ret;
}

signed main () {
for (int i = 1; i <= 1000000; i++) {
if (get(i * (i + 1) >> 1) >= 500) exit(printf("%lld\n", i * (i + 1) >> 1) * 0);
}
return 0;
}

#15. Lattice paths

显然是 2\times n\choose n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

#define int long long

int C(int n, int m) {
int ret = 1;
for (int i = 1; i <= m; i++)
ret = ret * (n - i + 1) / i;
return ret;
}

signed main () {
int n;
scanf("%lld", &n);
printf("%lld", C(2 * n, n));
return 0;
}

#73. Counting fractions in a range

直接上暴力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>

int main () {
int limit = 12000, ret = 0;
for (int d = 1; d <= limit; d++) {
for (int i = 1; i <= d; i++) {
if (std::__gcd(d, i) != 1) continue;
if (3 * i < d || 2 * i > d) continue;
ret++;
}
}
printf("%d", ret - 2);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!