欧拉计划个人题解(011-015)

algorithm
Project Euler, algorithm
文章目录
  1. 1. [011]Largest product in a grid
  2. 2. [012]Highly divisible triangular number
  3. 3. [013]Large sum
  4. 4. [014]Longest Collatz sequence
  5. 5. [015]Lattice paths

[011]Largest product in a grid

题意

在20*20的矩阵中，找4个同方向(横竖斜)的数字，使它们的乘积最大。

思路

直接做，注意对0的处理。

优化

$$
(1+2+…+100)^2 = \left( \frac{n \times (n+1)}{2} \right)^2 \\
(1^2 + 2^2 + … + 100^2) = \frac{n \times (n + 1) \times (2n+1)}{6}
$$

代码

C++\STL

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int main(void)
{
    for(int i = 0; i < 20; ++i)
        for(int j = 0; j < 20; ++j)
            cin >> maps[i][j];

    int ans = 0;
    int tmp;

    // horizontal
    for(int i = 0; i < 20; ++i)
        for(int j = 0; j < 20 - 4; ++j)
        {
            tmp = 1;
            for(int k = 0; k < 4; ++k)
                tmp *= maps[i][j+k];
            ans = max(ans,tmp);
        }
    // vertical
    for(int i = 0; i < 20 - 4; ++i)
        for(int j = 0; j < 20; ++j)
        {
            tmp = 1;
            for(int k = 0; k < 4; ++k)
                tmp *= maps[i+k][j];
            ans = max(ans,tmp);
        }

    // diagonal1
    for(int i = 0; i < 20 - 4; ++i)
        for(int j = 0; j < 20 - 4; ++j)
        {
            tmp = 1;
            for(int k = 0; k < 4; ++k)
                tmp *= maps[i+k][j+k];
            ans = max(ans,tmp);
        }
    // diagonal2

    for(int i = 3; i < 20; ++i)
        for(int j = 0; j < 20 - 4; ++j)
        {
            tmp = 1;
            for(int k = 0; k < 4; ++k)
                tmp *= maps[i-k][j+k];
            ans = max(ans,tmp);
        }

    cout << ans << endl;
    return 0;
}

答案

70600674

[012]Highly divisible triangular number

题意

三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是$1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$。那么三角形数序列中的前十个是：$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …$
下面我们列出前七个三角形数的约数：

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

可以看出28是第一个拥有超过5个约数的三角形数。
那么第一个拥有超过500个约数的三角形数是多少？

思路

一个根据题意找，注意可以开平方缩小范围。

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isaccepted(long long num)
{
    int factor_count = 0;
    long long upper = static_cast<long long>(sqrt(num));
    for(int i = 2; i < upper; ++i)
        if(num % i == 0)
            factor_count += 2;
    if(upper * upper == num)
        factor_count += 1;
    if(factor_count >= 500)
        return true;
    else
        return false;
}
int main(void)
{
    int ans = 1;
    int i = 1;
    while(!isaccepted(ans))
        ans += ++i;
    cout << ans << endl;
    return 0;
}

优化

但是上面的代码还是很慢，我们需要引入一个新的算法。

我们知道，一个数的因数，可以由一些质因数组合而成，那么一个数的因数个数与质因数会有关系，我们把一个数分解成若干个质因数，例如

$$
28 = 2^2 * 7^1
$$
则其组合的情况有

$$
2^0 \times 7^0 \\
2^1 \times 7^0 \\
2^2 \times 7^0 \\
2^0 \times 7^1 \\
2^1 \times 7^1 \\
2^2 \times 7^1 \\
$$
共计6种，其实就是$6 = 3 * 2 = (2 + 1) \times (1 + 1)$
即为各质因子指数加一的乘积，但剩下的算法有些看不懂，留待更新。1

答案

76576500

[013]Large sum

题意

给出一百个50位数字的数，计算出他们的和，结果只取前十位数。

思路

高精度加法。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class BigInt
{
public:
    const size_t SIZE = 60;

    BigInt();
    ~BigInt();
    BigInt(int num);
    BigInt(BigInt&& b);
    BigInt(const BigInt& b);
    BigInt& operator = (const BigInt&);
    bool operator == (const BigInt& b);
    void operator += (const BigInt& b);
    string toString();
    friend istream& operator >> (istream& in, BigInt& b)
    {
        string str;
        in >> str;
        auto p = str.rbegin();
        size_t postion = 0;
        while(p != str.rend())
        {
            b.m_num[postion] = (*p) - '0';
            ++postion;
            ++p;
        }
        return in;
    }
    friend ostream& operator <<(ostream& out, const BigInt& b)
    {
        size_t postion = b.SIZE - 1;
        while(b.m_num[postion] == 0 && postion != 0)
            --postion;
        while(postion != 0)
        {
            out << static_cast<int>(b.m_num[postion]);
            --postion;
        }
        out << static_cast<int>(b.m_num[0]);
        return out;
    }
private:
    char* m_num;
};

BigInt::BigInt()
{
    m_num = new char[SIZE];
    memset(m_num, 0, sizeof(char) * SIZE);
}

BigInt::~BigInt()
{
    if(m_num != nullptr)
        delete[] m_num;
}
BigInt::BigInt(int num)
{
    assert(num >= 0);
    m_num = new char[SIZE];
    memset(m_num, 0, sizeof(char) * SIZE);
    int p = 0;
    do{
        m_num[p] = num % 10;
        num /= 10;
        p++;
    }while(num != 0);
}
BigInt::BigInt(BigInt&& b)
{
    m_num = b.m_num;
    b.m_num = nullptr;
}
BigInt::BigInt(const BigInt& b)
{
    this->m_num = b.m_num;
}
bool
BigInt::operator==(const BigInt& b)
{
    for(size_t i = 0;i < SIZE; ++i)
        if(m_num[i] != b.m_num[i])
            return false;
    return true;
}
void
BigInt::operator+=(const BigInt& b)
{
    for(size_t i = 0; i < SIZE; ++i)
        m_num[i] += b.m_num[i];
    for(size_t i = 0; i < SIZE - 1; ++i)
    {
        m_num[i + 1] += m_num[i] / 10;
        m_num[i] = m_num[i] % 10;
    }
}
string
BigInt::toString()
{
    size_t postion = SIZE - 1;
    while(m_num[postion] == 0 && postion != 0)
        --postion;
    string str(postion + 1, '\0');
    auto p = str.begin();
    while(postion != 0)
    {
        (*p) = m_num[postion] + '0';
        --postion;
        ++p;
    }
    (*p) = m_num[postion] + '0';
    return str;
}
int main(void)
{
    BigInt sum,tmp;
    while(cin >> tmp)
        sum += tmp;
    cout << sum.toString().substr(0,10) << endl;
    return 0;
}

答案

5537376230

[014]Longest Collatz sequence

题意

3n+1猜想。猜想的内容如下：
对于一个正整数n，若其为偶数，则将其除2，若其为奇数，则将其乘三再加一，重复上述操作，直至这个数变为1。
题目问一百万(1e6)内，哪一个数需要进行的操作数最多，输出这个数。

思路

模拟，对每一个数都实际进行若干次操作，统计次数，输出。

优化

因为对于一个数来说，他操作的过程中，会演化成其他数，这些数字的次数同时也可以确认下来，那么我们就节约了计算这些数字的时间，就是一个记录的过程。

代码

C++\STL

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
38
39
const int MAXN = 1e6;
int num[MAXN+2];
int main(void)
{
    memset(num,0,sizeof(num));
    num[1] = 1;
    int ans = 1;
    stack<long long> s;
    for(int i = 1; i <= MAXN; ++i)
    {
        if(num[i] == 0)
        {
            s.push(i);
            long long tmp = i;
            int count;
            while(tmp != 1)
            {
                tmp = (tmp % 2) ? (3 * tmp + 1) : (tmp / 2);
                if(tmp <= MAXN && num[tmp] != 0)
                {
                    count = num[tmp];
                    while(!s.empty())
                    {
                        ++count;
                        if(s.top() <= MAXN)
                            num[s.top()] = count;
                        s.pop();
                    }
                    break;
                }
                s.push(tmp);
            }
        }
        if(num[ans] < num[i])
            ans = i;
    }
    cout << ans << endl;
    return 0;
}

答案

837799

[015]Lattice paths

题意

在一个方格内，从左上角，沿着线，可以选择向右走一段或向下走一段，直至右下角，计算不重复的路径数量。对于一个22的方格，答案是6种，现在问2020的方格有多少种可能。

思路

DP，之前想成了卡特兰数，细看发现规则不一样，于是有下面的代码。

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int MAXN = 21;
unsigned long long dp[MAXN][MAXN];
int main(void)
{
    dp[0][0] = 1;
    // init
    for(int i = 1; i < MAXN; ++i)
    {
        dp[i][0] = dp[i-1][0];
        dp[0][i] = dp[0][i-1];
    }
    for(int i = 1; i < MAXN; ++i)
        for(int j = 1; j < MAXN; ++j)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    cout << dp[MAXN-1][MAXN-1] << endl;

    return 0;
}

优化

其实这是一个简单的排列组合问题，路径的数量其实就是$C^{20}_{40}$
然后会爆空间，还可以做简化。

$$
\begin{align}
C^{20}_{40} &= \frac{40 \times 39 \times 38 … \times 21}{20 \times 19 \times 18 … \times 1} \\
&= \frac{39 \times 37 \times 35 … \times 21}{10 \times 9 \times 8 … \times 1} \times 2^{10}
\end{align}
$$
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(void)
{
    long long mo = 1LL;
    long long de = 1LL;
    for(int i = 1; i <= 10; ++i)
    {
        mo *= 19 + (i * 2);
        de *= i;
        long long tmp = gcd(mo,de);
        mo /= tmp;
        de /= tmp;
    }
    long long ans = mo * 1024 / de;
    cout << ans;
    return 0;

}

答案

137846528820