前言

本文仅记录自己的做题代码
题目合计点击此处
题解点击此处

Problem 1 - 3或5的倍数

解法一：枚举

#include <bits/stdc++.h>  
using namespace std;  

int main()
{
	int sum = 0; 
	for (int i = 1; i < 1000; i++)
		if (i % 3 == 0 || i % 5 == 0)	
			sum += i;
	
	cout << sum;
	return 0;
} 

解法二：容斥原理

分别求出1000以下所有3的倍数和5的倍数的和,再减去15的倍数的和

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int sum3 = (3 + 999) * (999 / 3) / 2;  // 求和公式(3是首项，999是末项，999/3是项数)
	int sum5 = (5 + 995) * (999 / 5) / 2;
	int sum15 = (15 + 990) * (999 / 15) / 2;
	cout << sum3 + sum5 - sum15;
	return 0;
} 

Problem 2 - 偶数斐波那契数

解法一：枚举

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a = 0, b = 1, s = 0, sum = 0;
	while (s <= 4000000)
	{
        if (s % 2 == 0)	sum += s;

		a = b;
		b = s;
		s = a + b;
	}
	cout << sum;
	return 0;
} 

解法二: 找规律

$F_n=4F_+F_$
其中$F_n$,$F_$,$F_$都为偶数。

则我们可以把它们表示成为一个新的数列，称为偶数斐波那契数列，第一项为二，第二项为八，递推公式如下：
$n$=$$+$EF_$($EF_1=2$, $EF_2=8$)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a = 2, b = 8, sum = 10, s;  // sum先初始化为前两项的和
	while (1) 
	{ 	
		s = 4 * b + a;
		a = b;  // 迭代
		b = s;
		
		if (s > 4000000)	break;
		sum += b;
	}
	cout << sum;
	return 0;
}

解法三：fibonacci通项公式（精度难以控制）

Problem 3 - 最大质因数

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n = 600851475143, res = 0;
    for (long long i = 2; i <= n / i; i++)
    {
        while (n % i == 0) 
        {
            n /= i;
            res = i;
        }
    }
    if (n > 1) res = n;
    
    cout << res;
    return 0;
}

Problem 4 - 最大回文乘积

Code

#include <bits/stdc++.h>
using namespace std;

int cnt[20];

void get_div(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        int s = 0;
        while (n % i == 0)
        {
            n /= i;
            s++;
        }
        cnt[i] = max(cnt[i], s);
    }
    if (n > 1) cnt[n] = max(cnt[n], 1);
}

int main()
{
    for (int i = 1; i <= 20; i++)
        get_div(i);

    long long res = 1;
    for (int i = 1; i <= 20; i++)
        res *= pow(i, cnt[i]);

    cout << res;
    return 0;
}

Problem 5 - 最小公倍数

Code 法一(暴力 很慢)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    for (long long i = 1;i <= 300000000; i++)
    {   
        bool flag = false;
        for (int j = 1;j <= 20;j++)
            if (i % j != 0)
            {
                flag = true;
                break;
            }
        if (!flag)
        {
            cout << i;
            return 0;
        }
    }
}

Code 法二

/*
1~20的最小公倍数其实就是他们的最高次数质因数相乘

问:如何理解是最高次数而不是总次数？
=>16分解质因数后为2的4次方
4分解质因数后为2的2次方
因为16是4的倍数，所以2的4次方是涵盖4的
所以2取出现的最高次，4次方,
*/
#include <bits/stdc++.h>
using namespace std;

int cnt[20];

void get_div(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        int s = 0;
        while (n % i == 0)
        {
            n /= i;
            s++;
        }
        cnt[i] = max(cnt[i], s);  // 只记录出现过的最高次数
    }
    if (n > 1) cnt[n] = max(cnt[n], 1);
}

int main()
{
    for (int i = 1; i <= 20; i++)  // 对1~20分解质因数
        get_div(i);

    long long res = 1;
    for (int i = 1; i <= 20; i++)
        res *= pow(i, cnt[i]);  // 将分解后每个质因数得到的最高次数代表的数相乘

    cout << res;
    return 0;
}

Problem 6 - 平方的和与和的平方之差

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n = 100;
    int sum1 = pow((1 + n) * n / 2, 2); // 和的平方公式
    int sum2 = n * (n + 1)* (2 * n + 1) / 6;  // 平凡的和公式

    cout << sum1 - sum2;
    return 0;
}

Problem 7 - 第10001个质数

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int cnt = 0;
    for (int i = 2; ; i++)
    {
        bool flag = true;
        for (int j = 2; j * j <= i; j++)
            if (i % j == 0) 
            {
                flag = false;
                break;
            }
        if (flag)
        {
            cnt++;
            if (cnt == 10001)
            {
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}