目录

欧垃计划Level-1解题总结

Euler-1 Multiples of 3 and 5

原题链接

思路
由于数据量很大,枚举肯定会超时,这道题可以用公式来解决。
一种是等差数列求和:
直接把小于n的所有3的倍数和5的倍数的和求出来,再减去15的倍数的和。
这三个和分别是以35,15)为首项,小于n35,15)的最大倍数为末项的等差数列的和。
然后在题目评论区看别人的方法,根据一个大佬的思路,我优化了我的代码,为了去掉等于n的那个倍数,我们可以直接这么求数列的末项:(n-1)/3,(n-1)/5,(n-1)/15
参考代码

我的实现:

#include <cstdio>

typedef long long LL;

int main(void)
{ 
    int T;
    scanf("%d", &T);
    while(T--)
    {
        LL n;
        scanf("%lld", &n);
        
        //等差数列求和,注意数列末项要小于n,等于n的那一项不能算进去
        LL sum_mul_3 = (3 + 3*((n-1)/3)) * ((n-1)/3) / 2;
        LL sum_mul_5 = (5 + 5*((n-1)/5)) * ((n-1)/5) / 2;
        LL sum_mul_15 = (15 + 15*((n-1)/15)) * ((n-1)/15) / 2;
        
        LL res = sum_mul_3 + sum_mul_5 - sum_mul_15;
        
        printf("%lld\n", res);
    }

    return 0;
}

Euler-2 Even Fibonacci numbers

原题链接

思路
法一:用斐波那契函数递推式按照题意递推,用滚动变量求和即可。
法二:由于题目只需要得到斐波那契数列偶数项的和,所以我们可以观察一下规律:
首先观察一下斐波那契前十五项:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610...
可以发现,第三项,第六项,第八项,第十一项等等项是偶数,也就是说,从第三项开始,每隔两项出现一个偶数项,这是由奇偶数相加的性质来的,奇数相加得偶数,奇偶相加得奇数,那么接下来推导一下:
由斐波那契定义可知:
$$F_n = F_{n-1} + F_{n-2}$$
将等式右边两项再往前递推一次,并合并同类项,可以得到:
$$F_n = 2F_{n-3} + F_{n-2} + F_{n-4}$$
再将等式右边三项中的后面两项往前递推一次,并合并同类项,可以得到:
$$F_n = 3F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6}$$
最后再将等式右边的$F_{n-4} + F_{n-5}$又合并为$F_{n-3}$,并合并同类项,可以得到:
$$F = 4F_{n-3} + F_{n-6}$$ 至此,我们得到了一项关于斐波那契数列偶数项的新数列,第一项为2,第二项为8。至此,就可以用这个递推式更高效地求解斐波那契数列中偶数项的和。
参考代码

法一代码:

#include <cstdio>

typedef long long LL;

int main(void)
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        LL n;
        scanf("%lld", &n);
        LL res = 2; //注意别漏掉起始项中的2
        LL f1 = 1, f2 = 2;
        LL fn = 0; //用fn来存储f1和f2滚动计算的结果
        while(fn <= n)
        {
            fn = f1 + f2; 
            if(fn % 2 == 0 && fn <= n) res += fn;
            f1 = f2;
            f2 = fn;
        }

        printf("%lld\n", res);
    }

    return 0;
}

法二代码:

#include <cstdio>

typedef long long LL;

int main(void)
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        LL n;
        scanf("%lld", &n);
        LL res = 10; //注意别漏掉开始的两项2和8
        LL f1 = 2, f2 = 8;
        LL fn = 0; //用fn来存储f1和f2滚动计算的结果
        while(fn <= n)
        {
            fn = f1 + 4 * f2; //注意递推式中下标的对应关系
            if(fn <= n) res += fn;
            f1 = f2;
            f2 = fn;
        }

        printf("%lld\n", res);
    }

    return 0;
}

Euler-3 Largest prime factor

原题链接

思路
顺序枚举质因子,取最大的那个即可。 可以证明,一个数n只有一个大于$\sqrt{n}$的质因子,所以枚举完小于的那一部分后,若还有剩下的质因子,那么这个质因子就是最大的。
参考代码
#include <cstdio>

typedef long long LL;

LL decompose(LL x)
{
    LL f;
    for(LL i = 2; i <= x / i; i++)
    {
        if(x % i == 0)
        {
            f = i;
            while(x % f == 0) x /= f;
        }
    }
    if(x > 1) return x; 
    else return f;
}

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        LL n;
        scanf("%lld", &n);
        LL max_prime_factor = decompose(n);
        printf("%lld\n", max_prime_factor);
    }

    return 0;
}

Euler-4 Largest palindrome product

原题链接

思路
预处理枚举出两个三位数能够乘出来的所有数字,检查是否为回文数,若是则存储到一个数组中。然后将数组从大到小排序,每次输入时只需要遍历数组找到第一个小于n的数字,即是所求范围内的最大的回文数。
注意不能直接枚举所有从100*100999*999所有数,因为里面会有质数,是无法由两个三位数乘出来的。并且在枚举乘积的时候必须要每个判断,因为枚举的时候并不是单调枚举的。
另外,如果能过保证所求回文数是偶数位的回文数(虽然这道题不是),可以先判断当前枚举的数是否为11的倍数再判断是不是回文数。可以证明,所有偶数位的回文数都能被11整除。
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1000010;
int a[maxn];
int cnt;

bool is_Palin(int x)
{
    int a = x / 100000, b = x % 100000 / 10000, c = x % 10000 / 1000;
    int A = x % 10, B = x % 100 / 10, C = x % 1000 / 100;
    
    if(a == A && b == B && c == C) 
        return true;
    
    return false;
}

bool cmp(int x, int y)
{
    return x > y;
}

void init(void)
{    
    for(int i = 999; i >= 100; i--)
        for(int j = 999; j >= 100; j--)
            if(is_Palin(i*j)) 
                a[cnt++] = i*j;
    sort(a, a + cnt, cmp); 
}

int find(int x)
{
    for(int i = 0; i < cnt; i++)
        if(a[i] < x)
            return a[i];
    
    return -1;
}

int main(void)
{   
    init();
    
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        
        int max_palin = find(n);
                    
        printf("%d\n", max_palin);
    }

    return 0;
}

Euler-5 Smallest multiple

原题链接

思路
法一:要能够被1~20中的所有数整除,直接求1~20的最小公倍数即可。
法二:对于2520这个数,我们分解质因数得到:
$$2520 = 2^3 \times 3^2 \times 5 \times 7$$
而对于题目中要求能够整除它的数2~10也分解质因数得到(本身是质数的数略):
$4 = 2 \times 2$, $6 = 2 \times 3$, $8 = 2 \times 2 \times 2$, $9 = 3 \times 3$, $10 = 2 \times 5$
可以发现,能被8整除的数,一定能被8的因子24整除,那么我们只需要分解质因数后,用各质因子的最高次幂相乘,即可得到答案。
法二在数据量较大($\geq 10000$)时,效率明显优于法一。 注意题目中输入包含N=1N=2的情况
参考代码

法一代码:

#include<cstdio>

typedef long long LL;

LL gcd(LL a, LL b)
{
    return (b == 0) ? a : gcd(b, a%b);
}

LL lcm(LL a, LL b)
{
    LL d = gcd(a, b);
    return a/d*b;
}

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        
        LL res = lcm(1, 2);
        if(n == 1) 
            res = 1;
        else if(n == 2) 
            res = 2;
        else if(n > 2)
            for(int i = 3; i <= n; i++) res = lcm(res, (LL)i);

        printf("%lld\n", res);
    }

    return 0;
}

法二代码:

#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 1000010;
typedef long long LL;
LL res = 1;
int primes[maxn];

void decompose(int x)
{
    for(int i = 2; i <= x / i; i++)
    {
        if(x % i == 0)
        {
            int f = i, s = 0;
            while(x % f == 0)
            {
                x /= f;
                s++;
            }
            if(s > primes[f])   //得到各质因子最高次幂
            {
                //在维护质因子幂的次数时就同时把结果中的质因子变成最高次幂
                int t = s - primes[f];
                while(t--) res *= i;
                primes[f] = s;  
            }
        }
    }
    if(x > 1 && !primes[x]) 
    {
        primes[x]++;
        res *= x;
    }
}

int main(void)
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        
        if(n < 2) 
            cout << n << endl;
        else 
        {
            //多组输入,每组都需要初始化
            res = 1;
            memset(primes, 0, sizeof(primes));
            
            for(int i = 2; i <= n; i++) decompose(i);
            cout << res << endl;
        }
    }

    return 0;
}

Euler-6 Sum square difference

原题链接

思路
法一:
直接枚举求和再相减即可。
法二:
推公式求和:
和的平方转化为先求1~n的等差序列的和,再平方。
平方和直接使用公式$\frac{n(n+1)(2n+1)}{6}$即可,最后两者相减即为:
$$ans = (\frac{(1+n)n}{2})^2 - \frac{n(n+1)(2n+1)}{6}$$
参考代码

法一代码:

#include <cstdio>

typedef long long LL;

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        LL sum_of_sq = 0, sq_sum = 0;
        for(LL i = 1; i <= n; i++)
        {
            sum_of_sq += i*i;
            sq_sum += i;
            if(i == n) sq_sum = sq_sum*sq_sum;
        }
        printf("%lld\n", sq_sum - sum_of_sq);
    }

    return 0;
}

法二代码:

#include <cstdio>

typedef long long LL;

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        LL n;
        scanf("%lld", &n);
        LL sum_of_sq = (n*(n+1)*(2*n+1)) / 6;
        LL sq_sum = ((1+n)*n / 2) * ((1+n)*n / 2); 
        printf("%lld\n", sq_sum - sum_of_sq);
    }

    return 0;
}

Euler-7 10001st prime

原题链接

思路

用的欧拉筛,注意要把素数表的范围开大一些。

  • 欧拉筛的讲解后续会更新
    更新后把链接补在这里。
参考代码
#include <cstdio>

const int maxn = 1000010;
typedef long long LL;
LL primes[maxn];
bool st[maxn];
int cnt;

void get_primes(void)
{
    for(LL i = 2; i <= maxn; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(LL j = 0; primes[j] <= maxn / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(void)
{
    get_primes();
    
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        printf("%lld\n", primes[n-1]);    //注意素数表下标是从0开始的
    }
    return 0;
}

Euler-8 Largest product in a series

原题链接

思路
找这个有n个数的序列中连续k个数的乘积最大,先将这串数字转化为字符串,再用二重循环遍历找所有连续k个数的乘积,看哪个最大即可。
欧拉计划官网题面是找连续13个数的最大乘积,所以会爆int,存储时需要用long long
参考代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int maxn = 1010;
char a[maxn];

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, k;
        scanf("%d %d", &n, &k);
        memset(a, 0, sizeof(a));
        scanf("%s", a);  
        
        LL res = 0;
        for(int i = 0; i < n - k; i++)
        {
            LL t = 1;
            for(int j = i; j < i + k; j++) t *= (LL)(a[j] - '0');
            res = max(t, res);
        }
        printf("%lld\n", res);
    }

    return 0;
}

Euler-9

参考资料

Euler-2法二
Euler-5法二