欧垃计划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;
}