欧拉计划大合集

Problem #1 Multiples of 3 or 5

Problem Description

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$.

Chinese / 3 或 5 的倍数

如果我们列出所有小于 $10$ 的 $3$ 或 $5$ 的倍数，我们会得到 $3、5、6$ 和 $9$。这些倍数的和是 $23$。

求所有小于 $1000$ 的 $3$ 或 $5$ 的倍数之和。

Solution

枚举每个数即可，答案为 $233168$ 。

Code

C++

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

int main(){
    ll ans=0;

    for(int i=1;i<1000;i++){
        if(i%3==0||i%5==0){
            ans += i;
        }
    }

    cout << ans << "\n";

    return 0;
}

Python

ans = 0

for i in range(1000):
    if i % 3 == 0 or i % 5 == 0:
        ans += i

print(ans)

Wolfram Language

answer = 0

For[i = 0, i < 1000, i++,
  If[Mod[i, 3] == 0 || Mod[i, 5] == 0,
    answer += i
  ]
]

Print[answer]

Problem #2 Even Fibonacci Numbers

Problem Description

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, \dots$$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Chinese / 偶斐波那契数

斐波那契数列中的每个新项都是通过将前两项相加而生成的。从 $1$ 和 $2$ 开始，前 $10$ 项分别是： $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$

考虑斐波那契数列中值不超过四百万的项，求其中为偶数的项之和。

Solution

也是直接模拟斐波那契数列即可，答案为 $4613732$ 。

Code

C++

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int LIMIT=4000000;

vector<int> fib;

int main(){
    ll ans=0;

    fib.push_back(1);
    fib.push_back(1);

    while(true){
        int nw=fib[fib.size()-1]+fib[fib.size()-2];
        if(nw>LIMIT){
            break;
        }
        if(nw%2==0){
            ans += nw;
        }
        fib.push_back(nw);
    }

    cout << ans << "\n";

    return 0;
}

Problem #3 Largest Prime Factor

Problem Description

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

What is the largest prime factor of the number $600851475143$?

Chinese / 最大质因子

$13195$ 的质因子是 $5、7、13$ 和 $29$。

数字 $600851475143$ 的最大质因子是多少?

Solution

枚举给定数的所有质因子即可，这里使用了 Miller–Rabin 素性测试。答案为 $6857$ 。

Code

C++

#include <iostream>
#include <random>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ll NUM=600851475143;

random_device rd;
mt19937_64 gen(rd());

ll randll(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(gen);
}

ll qpow(ll a,ll b,ll P){
    ll res=1;
    while(b!=0){
        if(b&1){
            res *= a;
            res %= P;
        }
        a *= a;
        a %= P;
        b >>= 1;
    }
    return res;
}

bool millerRabin(ll n){
    constexpr ll TEST_TIME=10;

    if(n<3||n%2==0){
        return n==2;
    }

    if(n%3==0){
        return n==3;
    }

    ll u=n-1,t=0;
    while(u%2==0){
        u /= 2;
        t++;
    }

    for(ll i=1;i<=TEST_TIME;i++){
        ll a=randll(0,n-4)+2,v=qpow(a,u,n);
        if(v==1){
            continue;
        }
        ll s;
        for(s=0;s<t;s++){
            if(v==n-1){
                break;
            }
            v = (ll)v*v%n;
        }
        if(s==t){
            return false;
        }
    }

    return true;
}

vector<int> fac;

signed main(){
    // 775146
    int sqrtn=sqrt(NUM);

    for(int i=1;i<=sqrtn;i++){
        if(NUM%i==0){
            if(millerRabin(NUM/i)){
                cout << NUM/i << "\n";
                return 0;
            }
            if(millerRabin(i)){
                fac.push_back(i);
            }
        }
    }

    cout << fac.back() << "\n";

    return 0;
}

Problem #4 Largest Palindrome Product

Problem Description

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

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

Chinese / 最大回文乘积

回文数从两个方向读都是相同的。由两个 $2$ 位数的乘积构成的最大回文数是 $9009 = 91 \times 99$。

求由两个 $3$ 位数的乘积构成的最大回文数。

Solution

枚举便可，答案为 $906609$ 。

Code

C++

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

bool judge(int num){
    string snum=to_string(num);
    int i=0,j=snum.size()-1;
    while(i<=j){
        if(snum[i]!=snum[j]){
            return false;
        }
        i++;
        j--;
    }
    return true;
}

int main(){
    int ans=0;

    for(int i=999;i>=100;i--){
        for(int j=999;j>=100;j--){
            if(judge(i*j)){
                ans = max(ans,i*j);
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Problem #5 Smallest Multiple

Problem Description

$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 divisibledivisible with no remainder by all of the numbers from $1$ to $20$?

Chinese / 最小公倍数

$2520$ 是能被从 $1$ 到 $10$ 的每个数整除的最小数。

能被从 $1$ 到 $20$ 的所有数整除的最小正数是多少?

Solution

题意转化为求 $1$ 到 $20$ 的最小公倍数。我们用 $\gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公因数， $\mathrm{lcm}(a,b)$ 代表最小公倍数。

$\mathrm{lcm}(a,b) = \frac{ab}{\gcd(a,b)}$

答案为 $232792560$ 。

Code

C++

#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}

constexpr int N=20;

int main(){
    ll ans=1;

    for(int i=2;i<=N;i++){
        ans = lcm(ans,i);
    }

    cout << ans << "\n";

    return 0;
}

Problem #6 Sum Square Difference

Problem Description

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.

Chinese / 平方和与和平方之差

前十个自然数的平方和是

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

前十个自然数的和的平方是

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

因此，前十个自然数的平方和与和的平方之间的差是 $3025 - 385 = 2640$。

求前一百个自然数的平方和与和的平方之间的差。

Solution

我们有如下两个公式。

$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

$\sum_{i=1}^{n} i = \frac{(1+n)*n}{2}$

答案为 $25164150$ 。

Code

C++

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int N=100;

int main(){
    cout << abs(N*(N+1)*(2*N+1)/6-((1+N)*N/2)*((1+N)*N/2)) << "\n";

    return 0;
}

Problem #7 10 001st Prime

Problem Description

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

What is the $10\,001$st prime number?

Chinese / 第 10001 个质数

列出前六个质数：$2、3、5、7、11$ 和 $13$，我们可以看到第 $6$ 个质数是 $13$。

第 $10001$ 个质数是多少?

Solution

使用线性筛解决，答案为 $104743$ 。

Code

C++

#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int N=10001;

vector<int> prms;
bitset<100000005> notp;

int main(){
    for(int i=2;;i++){
        if(!notp[i]){
            prms.push_back(i);
            if(prms.size()>=N){
                break;
            }
        }
        for(int prm:prms){
            if(prm*i>100000000){
                break;
            }
            notp[prm*i] = true;
            if(i%prm==0){
                break;
            }
        }
    }

    cout << prms.back() << "\n";

    return 0;
}

Problem #8 Largest Product in a Series

Problem Description

The four adjacent digits in the $1000$-digit number that have the greatest product are $9 \times 9 \times 8 \times 9 = 5832$.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the $1000$-digit number that have the greatest product. What is the value of this product?

Chinese / 连续数字最大乘积

在这个 $1000$ 位数字中,乘积最大的四个相邻数字是 $9 \times 9 \times 8 \times 9 = 5832$。

在这个 $1000$ 位数字中找出乘积最大的十三个相邻数字。这个乘积的值是多少?

Solution

暴力枚举即可，答案为 $23514624000$ 。

Code

C++

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int N=1000,M=13;

string num="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

int main(){
    num = ' '+num;

    ll ans=1;

    for(int i=1;i<=N-M+1;i++){
        ll cur=1;
        for(int j=i;j<=i+M-1;j++){
            cur *= num[j]-'0';
        }
        ans = max(ans,cur);
    }

    cout << ans << "\n";

    return 0;
}

Problem #9 Special Pythagorean Triplet

Problem Description

A Pythagorean triplet is a set of three natural numbers, $a \lt b \lt c$, for which, $$a^2 + b^2 = c^2.$$

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

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

Chinese / 特殊毕达哥拉斯三元组

勾股数是一组三个自然数，$a \lt b \lt c$，满足 $$a^2 + b^2 = c^2.$$

例如，$3^2 + 4^2 = 9 + 16 = 25 = 5^2$。

存在唯一一组勾股数满足 $a + b + c = 1000$。
求这组勾股数的乘积 $abc$。

Solution

直接枚举 $a$ 和 $b$ ，计算 $c$ 并判断合法性。答案为 $31875000$ 。

Code

C++

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

int main(){
    for(int a=1;a<=1000;a++){
        for(int b=a+1;b<1000-a-b;b++){
            int c=1000-a-b;
            if(a*a+b*b==c*c){
                cout << a*b*c << "\n";
                return 0;
            }
        }
    }

    return 0;
}

Problem #10 Summation of Primes

Problem Description

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

Find the sum of all the primes below two million.

Chinese / 质数求和

小于 $10$ 的质数之和是 $2 + 3 + 5 + 7 = 17$。

求小于两百万的所有质数之和。

Solution

使用线性筛筛一遍就可，答案为 $142913828922$ 。

Code

C++

#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int N=2000000;

vector<int> prms;
bitset<N+5> notp;

int main(){
    ull ans=0;

    for(int i=2;i<=N;i++){
        if(!notp[i]){
            prms.push_back(i);
            ans += i;
        }
        for(int prm:prms){
            if(i*prm>N){
                break;
            }
            notp[i*prm] = true;
            if(i%prm==0){
                break;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Problem #11 Largest Product in a Grid

Problem Description

In the $20 \times 20$ grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is $26 \times 63 \times 78 \times 14 = 1788696$.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the $20 \times 20$ grid?

Chinese / 方阵中的最大乘积

在下面的 $20 \times 20$ 的方阵中，有四个呈对角线排列的数被标记为红色。

这些数字的乘积是 $26 \times 63 \times 78 \times 14 = 1788696$。

在 $20 \times 20$ 的方阵中，四个呈一直线（竖直、水平或对角线）的相邻的数的最大乘积是多少？

Solution

枚举所有可能的情况即可，答案为 $70600674$ 。

Code

C++

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int NUM[20][20]={
    {8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8},
    {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0},
    {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65},
    {52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91},
    {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
    {24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50},
    {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
    {67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21},
    {24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
    {21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95},
    {78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92},
    {16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57},
    {86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58},
    {19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40},
    {4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66},
    {88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69},
    {4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36},
    {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16},
    {20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54},
    {1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48}
};

int main(){
    ull ans=0;

    for(int i=0;i<20;i++){
        for(int j=0;j<17;j++){
            ull cans=1;
            for(int k=j;k<j+4;k++){
                cans *= NUM[i][k];
            }
            ans = max(ans,cans);
        }
    }

    for(int i=0;i<17;i++){
        for(int j=0;j<20;j++){
            ull cans=1;
            for(int k=i;k<i+4;k++){
                cans *= NUM[k][j];
            }
            ans = max(ans,cans);
        }
    }

    for(int i=0;i<17;i++){
        for(int j=0;j<17;j++){
            ull cans=1;
            for(int k=i,l=j;k<i+4&&l<j+4;k++,l++){
                cans *= NUM[k][l];
            }
            ans = max(ans,cans);
            cans = 1;
            for(int k=i+3,l=j;k>=i&&l<j+4;k--,l++){
                cans *= NUM[k][l];
            }
            ans = max(ans,cans);
        }
    }

    cout << ans << "\n";

    return 0;
}

Problem #12 Highly Divisible Triangular Number

Problem Description

The sequence of triangle numbers is generated by adding the natural numbers. So the $7$^th 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, \dots$$

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

$$\begin{align} \mathbf 1 &\colon 1\\ \mathbf 3 &\colon 1,3\\ \mathbf 6 &\colon 1,2,3,6\\ \mathbf{10} &\colon 1,2,5,10\\ \mathbf{15} &\colon 1,3,5,15\\ \mathbf{21} &\colon 1,3,7,21\\ \mathbf{28} &\colon 1,2,4,7,14,28 \end{align}$$

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?

Chinese / 有很多因数的三角形数

三角形数是通过连续累加自然数得到的。例如第 $7$ 个三角形数是 $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$。前十个三角形数是： $$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$$

让我们列出前七个三角形数的所有因数：

我们可以看到 $28$ 是第一个拥有超过五个因数的三角形数。

第一个拥有超过五百个因数的三角形数的值是多少？

Solution

枚举数并判断其因数个数即可，答案为 $76576500$ 。

Code

C++

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

int fac(ll u){
    int res=0;
    for(int i=1;i<=sqrt(u);i++){
        if(u%i==0){
            if(i==sqrt(u)){
                res++;
            }
            else{
                res += 2;
            }
        }
    }
    return res;
}

int main(){
    ll cur=0;

    for(int i=1;;i++){
        cur += i;
        if(fac(cur)>500){
            cout << cur << "\n";
            break;
        }
    }

    return 0;
}