欧拉计划个人题解(001-005)

2018-06-11

algorithm

Project Euler, algorithm

文章目录

1. [001]Multiples of 3 and 5
2. [002]Even Fibonacci numbers
3. [003]Largest prime factor
4. [004]Largest palindrome product
5. [005]Smallest multiple

[001]Multiples of 3 and 5

题意

找寻[1,1000)以内，是3的倍数，或是5的倍数的数。

思路

暴力搜索判定

优化

容斥，先计算3的倍数在1000内有多少个，然后用等差公式计算出1000内3的倍数的和，同理有5的倍数，两者相加，重复的数用15的倍数的和减去即可。

代码

C++\STL

long long SumOf(long long up, int k)
{
    long long cnt = (up - 1) / k;
    return (k + cnt * k) * cnt / 2;
}
int main()
{
    long long n;
    cin >> n;
    cout << SumOf(n, 5) + SumOf(n, 7) - SumOf(n, 35) << endl;
    return 0;
}

答案

233168

[002]Even Fibonacci numbers

题意

斐波那契数列:

F[1] = 1
F[2] = 1
F[3] = 2
...

求斐波那契数列中数字为偶数的所有数字之和，数字不大于400万。

思路

递推暴力

C++\STL

int main()
{
    int ans = 0;
    int a = 1, b = 1, c = 2;

    while(c <= 4000000)
    {
        ans += c;
        a = b + c;
        b = a + c;
        c = a + b;
    }

    cout << ans << endl;
}

优化

列表找规律：

F[1] =  1     F[2] = 1
F[3] =  2     F[4] = 3
F[5] =  5     F[6] = 8
F[7] =  13    F[8] = 21
F[9] =  34    F[10] = 55
F[11] = 89    F[12] = 144
F[13] = 233   F[14] = 377
F[15] = 610   F[16] = 987
F[17] = 1597  F[18] = 2584

符合题意的有

F[3] = 2
F[6] = 8
F[9] = 34
F[12] = 144
F[11] = 610
F[18] = 2584

观察可得 F[n] = 4 * F[n-3] + F[n - 6]

正确性可以由斐波那契数列定义推出：

$$
\begin{align}
F_n &= F_{n-1} + F_{n-2} \\
& = F_{n-2} + F_{n-3} + F_{n-2} = 2 \times F_{n-2} + F_{n-3} \\
& = 2 \times ( F_{n-3} + F_{n-4} ) + F_{n-3} ) = 3 \times F_{n-3} + 2 \times F_{n-4} \\
& = 3 \times F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6} \\
& = 4 \times F_{n-3} + F_{n-6} \\
\end{align}
$$
代码

C++\STL

int main()
{
    int a[3] = {2,8,34};
    int ans = 0;
    int p = 2;
    while(a[p] < 4000000)
    {
        ans += a[p];
        p = (p + 1) % 3;
        a[p] = 4 * a[(p + 2) % 3] + a[(p + 1) % 3];
    }
    cout << ans << endl;
}

答案

4613732

[003]Largest prime factor

题意

求 600851475143 最大的质因子

思路

刚开始先暴力的，发现循环判定再循环判定复杂度就太高了。于是用埃氏筛法扫过去就行了。

代码

C++\STL

int Eratosthenes()
{
    const long long TARGET = 600851475143LL;
    const int upper = static_cast<const int>(sqrt(TARGET));
    bool *num = new bool[static_cast<unsigned long long>(upper)];
    memset(num, false, sizeof(bool) * static_cast<unsigned long long>(upper));
    int ans = 2;
    for(int i = ans; i < upper; ++i)
    {
        if(num[i] == false)
        {
            int p = 2;
            while(i * p < upper)
            {
                num[ i * p ] = true;
                ++p;
            }
            if(TARGET % i == 0)
                ans = i;
        }
    }
    delete[] num;
    return ans;
}

int main(void)
{
    int ans = Eratosthenes();
    cout << ans << endl;
    return 0;
}

答案

6857

[004]Largest palindrome product

题意

对于一个回文数，如：9009 = 91 × 99，他是由两个两位数构成的。现在找两个三位数能构成的最大回文数。

思路

首先是构造回文数，它符合一下几个规律：

六位数
六位数里面最大的
前三位和后三位对应相同

由上，我们将回文数按位拆分，枚举前一二三位，做对应就行了。值得一提的是第一位不可能为0，二三位都有可能为0。

优化

回文数必然可以被11整除，证明如下：回文数的形式必然为：

100000a + 10000b + 1000c + 100c + 10b + a
=100001a + 10010b + 1100c
因为：
100001 % 11 = 0
10010 % 11 = 0
1100 % 11 = 0
所以：
回文数必然可以被11整除

代码

C++\STL

int main()
{
    int num;
    int mark = 1;
    for(int i = 9; i >= 1 && mark; --i)
        for(int j = 9; j >= 0 && mark; --j)
            for(int k = 9; k >= 0 && mark; --k)
            {
                num = i*100 + j * 10 + k;
                num = num * 1000 + k * 100 + j * 10 + i;
                for(int t = 999; t >= 100 && mark; --t)
                    if(num % t == 0 && num / t >= 100 && num / t < 1000)
                    {
                        cout << num << endl;
                        mark = 0;
                    }
            }
    return 0;
}

答案

906609

[005]Smallest multiple

题意

2520是最小的能被1-10中每个数字整除的正整数。最小的能被1-20中每个数整除的正整数是多少？

思路

刚开始想直接找到20以内的质数2,3,5,7…相乘得出答案的，后来交了发现不对，尝试了一次，发现在4的时候就不能整除了。后来百度搜了一下，要：

列出20以内的质数，并求这些质数的小于20的最高次幂
再将这些质数的最高次幂的积相乘

于是有了下面的代码。

代码

C++\STL

bool check(vector<int>& s, int num)
{
    for(int e : s)
        if(num % e == 0)
            return false;
    return true;
}
int main(void)
{
    vector<int> s;
    for(int i = 2; i <= 20; ++i)
        if(check(s,i))
            s.push_back(i);
    long long ans = 1LL;
    for(int e : s)
    {
        int m = 1;
        while(m * e <= 20)
            m *= e;
        ans *= m;
    }
    cout << ans << endl;
    return 0;
}

答案

232792560