欧垃计划Level-1解题总结
目录
Euler-1 Multiples of 3 and 5
思路
由于数据量很大，枚举肯定会超时，这道题可以用公式来解决。
一种是等差数列求和：
直接把小于
这三个和分别是以
然后在题目评论区看别人的方法，根据一个大佬的思路，我优化了我的代码，为了去掉等于
一种是等差数列求和：
直接把小于
n的所有3的倍数和5的倍数的和求出来，再减去15的倍数的和。这三个和分别是以
3（5,15）为首项，小于n的3（5,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
思路
法一：用斐波那契函数递推式按照题意递推，用滚动变量求和即可。
法二：由于题目只需要得到斐波那契数列偶数项的和，所以我们可以观察一下规律：
首先观察一下斐波那契前十五项：
可以发现，第三项，第六项，第八项，第十一项等等项是偶数，也就是说，从第三项开始，每隔两项出现一个偶数项，这是由奇偶数相加的性质来的，奇数相加得偶数，奇偶相加得奇数，那么接下来推导一下：
由斐波那契定义可知：
$$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}$$ 至此，我们得到了一项关于斐波那契数列偶数项的新数列，第一项为
法二：由于题目只需要得到斐波那契数列偶数项的和，所以我们可以观察一下规律：
首先观察一下斐波那契前十五项：
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
思路
预处理枚举出两个三位数能够乘出来的所有数字，检查是否为回文数，若是则存储到一个数组中。然后将数组从大到小排序，每次输入时只需要遍历数组找到第一个小于
注意不能直接枚举所有从
另外，如果能过保证所求回文数是偶数位的回文数（虽然这道题不是），可以先判断当前枚举的数是否为11的倍数再判断是不是回文数。可以证明，所有偶数位的回文数都能被11整除。
n的数字，即是所求范围内的最大的回文数。注意不能直接枚举所有从
100*100到999*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
思路
法一：要能够被
法二：对于2520这个数，我们分解质因数得到：
$$2520 = 2^3 \times 3^2 \times 5 \times 7$$
而对于题目中要求能够整除它的数
$4 = 2 \times 2$, $6 = 2 \times 3$, $8 = 2 \times 2 \times 2$, $9 = 3 \times 3$, $10 = 2 \times 5$
可以发现，能被
法二在数据量较大（$\geq 10000$）时，效率明显优于法一。 注意题目中输入包含
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的因子2和4整除，那么我们只需要分解质因数后，用各质因子的最高次幂相乘，即可得到答案。法二在数据量较大（$\geq 10000$）时，效率明显优于法一。 注意题目中输入包含
N=1和N=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
思路
法一：
直接枚举求和再相减即可。
法二：
推公式求和：
和的平方转化为先求
平方和直接使用公式$\frac{n(n+1)(2n+1)}{6}$即可，最后两者相减即为：
$$ans = (\frac{(1+n)n}{2})^2 - \frac{n(n+1)(2n+1)}{6}$$
直接枚举求和再相减即可。
法二：
推公式求和：
和的平方转化为先求
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;
}