欧拉计划个人题解(006-010)

2018-06-11

algorithm

Project Euler, algorithm

文章目录

1. [006]Sum square difference
2. [007]10001st prime
3. [008]Largest product in a series
4. [009]Special Pythagorean triplet
5. [010]Summation of primes

[006]Sum square difference

题意

计算$(1 + 2 + … + 100)^2 - (1^2 + 2^2 + … + 100^2)$的结果。

思路

暴力做

优化

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

int main(void)
{
    const int n = 100;
    int a = n * (n+1) / 2;
    a *= a;
    int b = n * (n+1) * (2*n+1) / 6;
    cout << a - b << endl;
    return 0;
}

答案

25164150

[007]10001st prime

题意

找第10001个质数。

思路

直接筛选，但是判定素数函数有很多优化可以做。

代码

C++\STL

bool isprime(int n)
{
    if(n == 1)
        return false;
    if(n < 4)
        return true;
    if(n % 2 == 0)
        return false;
    if(n < 9)
        return true;
    if(n % 3 == 0)
        return false;
    int upper = static_cast<int>(sqrt(n));
    for(int i = 5; i <= upper;)
    {
        if(n % i == 0 || n % (i+2) == 0)
            return false;
        i += 6;
    }
    return true;
}

int main(void)
{
    int num = 1;
    int count = 0;
    int limit = 10001;
    while(count < limit)
    {
        ++num;
        if(isprime(num))
            ++count;
    }
    cout << num << endl;
    return 0;
}

答案

104743

[008]Largest product in a series

题意

有1000个数字，找其中连续的13个数字，求其最大值。

思路

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

代码

char maps[20 * 51];
int main(void)
{
    for(int i = 0; i < 20; ++i)
        scanf("%s",maps + (i * 50));
    for(int i = 0; i < 20 * 50; ++i)
            maps[i] -= '0';
    long long maxs = -1LL;
    long long tmp = 1LL;

    int count = 0;
    for(int i = 0; i < 20 * 50; ++i)
    {
        if(maps[i] == 0)
        {
            count = 0;
            tmp = 1LL;
            continue;
        }
        tmp *= maps[i];
        ++count;
        if(count > 13)
        {
            tmp /= maps[i-13];
            --count;
        }
        if(count == 13)
        {
            maxs = max(maxs, tmp);
        }
    }

    cout << maxs << endl;
    return 0;
}

答案

23514624000

[009]Special Pythagorean triplet

题意

求符合

$$
\begin{align}
a^2 + b^2 &= c^2 \\
a + b + c &= 1000 \\
a < b < c
\end{align}
$$
的$a \times b \times c$。

思路

易想到，将$c = 1000 - a - b$代换到一式中，然后二重循环扫描得出结果。

于是有下面的代码，

C++\STL

int main(void)
{
    for(int b = 1; b < 1000; ++b)
        for(int a = 1; a < b; ++a)
            if(1000000 - 2000*(a+b) + 2*a*b == 0)
            {
                cout << 1LL * a * b * (1000-a-b) << endl;
                break;
            }
    return 0;
}

优化

翻译节选自欧拉计划官网题解¹，许多地方有词不达意的情况。

9.2 勾股三角形参数化

一组勾股三角形(a,b,c)当$gcd(a,b,c) = 1$的情况下，被定义为原始/原生的。因为任意勾股三角形有$gcd(a,b) = gcd(b,c) = gcd(c,a)$的性质，而当且仅当$gcd(a,b) = 1$，这样的一个三角形才是原始/原始的。正如古希腊人所知道的，所有原始/原生的勾股三角形可以被表示为
$$
\begin{align}
(9.1) \\
a &= m^2 - n^2 \\
b &= 2 \times m \times n \\
c &= m^2 + n^2 \\
\end{align}
$$
此时$0 < n < m$，也许要交换$a$和$b$使得$a < b$。这些方程总是可以构造出一个勾股三角形，但是当且仅当有确切的一组$m,n$为偶数且$gcd(m,n) = 1$，才会被视作原始/原生的。
从任意一个勾股三角形你可以取得一个原始/原生的三角形，然后除去一个最大公因数，所以每一个勾股三角形有一个独一无二的表示：
$$
\begin{align}
(9.2) \\
a &= (m^2 - n^2) \times d \\
b &= 2 \times m \times n \times d \\
c &= (m^2 + n^2) \times d \\
\end{align}
$$
此时$0 < n < m$，且$gcd(m,n) = 1$，并且有确切的一组$m,n$为偶数，$d$代表$a,b,c$的最大公因数。

将其参数化后，我们可以得到
$$
(9.3) \\
a + b + c = 2 \times m \times (m + n) \times d
$$
所以为了找一个勾股三角形(a,b,c) 且 $a + b + c = s$，我们需要找到一个$\frac{s}{2}$的因子$m (> 1)$ 和一个$\frac{s}{2m}$奇数因子$k (=m+n)$，同时满足$m < k < 2m$和$gcd(m,k) = 1$，然后设$n = k - m$，$d = \frac{s}{2mk}$，联立(9.2)，可得出答案。

一个简单恰当的算法实现如下：

C++\STL

int gcd(int a, int b)
{
    return (b != 0) ? gcd(b,a%b) : a;
}
int main(void)
{
    int s2 = 1000 / 2;
    int mlimit = static_cast<int>( ceil(sqrt(s2)) ) - 1;
    for(int m = 2; m <= mlimit; ++m)
        if(s2 % m == 0)
        {
            int sm = s2 / m;
            while(sm % 2 == 0)
                sm = sm / 2;
            int k;
            if(m % 2 == 1)
                k = m + 2;
            else
                k = m + 1;
            while( k < 2 * m && k <= sm )
            {
                if(sm % k == 0 && gcd(k, m) == 1)
                {
                    int d = s2 / (k*m);
                    int n = k - m;
                    int a = d * (m * m - n * n);
                    int b = 2 * d * m * n;
                    int c = d * (m * m + n * n);
                    printf("%d %d %d %d",a,b,c,a*b*c);
                    return 0;
                }
                k += 2;
            }
        }
    return 0;
}

答案

31875000

[010]Summation of primes

题意

计算二百万(2e6)内的所有质数和。

思路

埃式筛。

代码

C++\STL

void sieve(vector<int>& v, const int upper)
{
    bool *num = new bool[static_cast<unsigned long long>(upper)];
    memset(num, false, sizeof(bool) * upper);
    for(int i = 2; i <= upper; ++i)
    {
        if(num[i] == false)
        {
            v.push_back(i);
            int p = 2;
            while(i * p < upper)
            {
                num[i*p] = true;
                ++p;
            }
        }
    }
    delete[] num;
}
int main(void)
{
    vector<int> v;
    const int upper = 2e6;
    sieve(v,upper+1);
    long long sum = 0;
    for(auto i : v)
        sum += i;
    cout << sum << endl;
    return 0;
}

答案

142913828922

1.https://projecteuler.net/overview=009 ↩