精华内容
下载资源
问答
  • 欧拉计划

    2021-01-18 17:41:29
    欧拉计划 1 10以下的自然数中,属于3和5的倍数的有3,5,6和9,它们之和是23. 找出1000以下的自然数中,属于3和5的倍数的数字之和。 #include <iostream> #include <bits/stdc++.h> using namespace std...

    欧拉计划

    • 1
      10以下的自然数中,属于3和5的倍数的有3,5,6和9,它们之和是23.
      找出1000以下的自然数中,属于3和5的倍数的数字之和。
    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    #define N 1000
    int main()
    {
        long long ans=0;
        long long l=(3+(N-1)/3*3)*((N-1)/3)/2;
        ans+=l;
        l=(5+(N-1)/5*5)*((N-1)/5)/2;
        ans+=l;
        l=(15+(N-1)/15*15)*((N-1)/15)/2;
        ans-=l;
        printf("%lld\n",ans);
        return 0;
    }
    
    
    • 2
      斐波那契数列中的每一项被定义为前两项之和。从 1 和 2 开始,斐波那契数列的前十项为:
      1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
      考虑斐波那契数列中数值不超过 4 百万的项,找出这些项中值为偶数的项之和。
    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    /*
    斐波那契数列中的每一个新项都是通过将前两项相加而生成的。从1和2开始,前10个术语将是:
    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
    通过考虑斐波那契数列中值不超过400万的项,求偶数项之和。
    */
    int main()
    {
        long long ans=2,a=1,b=2,c=0;
        while(b<=4000000)
        {
            c=b;
            b=a+b;
            a=c;
            //printf("%lld %lld %lld %lld\n",i,a,b,c);
            if(b%2==0)ans+=b;
        }
        printf("%lld\n",ans);
        return 0;
    }
    
    
    • 3
      最大质因数
      思路:从i=2开始除去所有因数,直到n=i
    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    /*
    13195的质数因子有5,7,13和29.
    600851475143的最大质数因子是多少?
    */
    void fun(long long n)
    {
        long long i=2,ans=n;
        while(i<n)
        {
            if(n%i==0)n=n/i;
            else {i++;ans=n;}
        }ans=n;
        printf("%d\n",ans);
    }
    int main()
    {
        long long n;
        while(scanf("%lld",&n)!=-1)
        fun(n);
        return 0;
    }
    
    
    展开全文
  • 欧拉计划题目50题

    2018-01-10 11:07:36
    欧拉计划经典题目,用于练习,一共60题。欧拉计划经典题目,用于练习,一共60题
  • ProjectEuler 欧拉计划问题解决方案
  • 欧拉计划 刷题计划提升编码能力

    欧拉计划

    Problem01等差数列公式

    在这里插入图片描述

    利用等差数列来做

    #include<stdio.h>
    int main() {
       int sum3 = (3 + 999) * 333 / 2;
       int sum5 = (5 + 995) * (995 / 5) / 2;
       int sum15 = (15 + (999 / 15) * 15) * (999 / 15) / 2;
       printf("%d\n", sum3 + sum5 - sum15);
       return 0;
    }
    

    Problem02滚动数组求斐波那契数

    在这里插入图片描述


    每一项约为前一项的1.5倍

    方法一:可以推导出400000大约在44项左右

    #include <stdio.h>
    #define MAX_N 44
    #define N 4000000
    
    int fib[MAX_N + 5];
    
    int main() {
        fib[1] = 1,
        fib[2] = 2;
        long long sum = 2;
        for(int i = 3; i <= MAX_N && fib[i - 1] + fib[i - 2] <= N; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
            if(fib[i] & 1) continue;
            sum += fib[i];
        
        }
        printf("%lld\n", sum);
        return 0;
    }
    

    方法二:

    #include<stdio.h>
    #define N 4000000
    
    int main() {
        int sum = 0, n = 0;
        int a = 0, b = 1, c;
        while(a + b <= N) {
            n += 1;
            b = a + b;
            a = b - a;
            if(b & 1) continue;
            sum += b;
        }
        printf("n = %d, sum = %d\n", n, sum);
        return 0;
    }
    

    方法三:滚动数组, 循环利用3个空间


    F[i%3]=F[(i1)%3]+F[(i2)%3]F[i]=F[i1]+F[i2]F[i\%3] = F[(i -1)\%3] + F[(i - 2)\%3]\\等价于\\ F[i] = F[i-1] + F[i - 2]

    #include <iostream>
    using namespace std;
    int main() {
    	int a[3]={0, 1, 2};
    	int sum = 0;
    	for(int i = 2; a[(i - 1) % 3] + a[(i - 2) % 3] <= 4000000; ++i) {
    		a[i % 3] = a[(i - 1) % 3] + a[(i - 2) % 3];
    		if(a[i % 3] % 2 == 0) sum += a[i % 3];
    	}
    	cout << sum;
    	return 0;
    }
    
    #include<stdio.h>
    #define N 4000000
    
    int main() {
        int fib[3] = {0, 1};
        int sum = 0, n = 2;
        while(fib[(n - 1) % 3] + fib[(n - 2) % 3] <= N) {
            fib[n % 3] = fib[(n - 1) % 3] + fib[(n - 2) % 3];
            if(!(fib[n % 3] & 1)) sum += fib[n % 3];
            n += 1;
        }
        printf("%d\n", sum);
        return 0;
    }
    
    

    Problem03最大质因子

    在这里插入图片描述

    对于任意合数 n = a * b (a > 1, b > 1)
    假设 a<=ba <= b, 则 a<=n,b>=n;a <= \sqrt n, b >= \sqrt n;

    #include <stdio.h>
    #define N 600851475143LL //LL识别长整型
    int main() {
        long long ans = 0, M = N;
        long long i = 2;
        while(i * i <= M) {
            if(M % i == 0) ans = i;//ans一定是素因子
            while(M % i == 0) M /= i;
            i += 1;
        }
        //如果M是合数的话,在循环内一定会除到1
        if(M > 1) ans = M; //此行的必要
        printf("%lld\n", ans);
        return 0;
    }
    

    Problem04最大回文乘积 回文数

    在这里插入图片描述

    #include <stdio.h>
    int is_val(int n) {
        int x = n;
        int temp = 0;
        while(x) {
            temp = temp * 10 + x % 10;
            x /= 10;
        }
        return temp == n;
    }
    
    int main() {
        int ans = 0;
        for(int i = 100; i < 1000; ++i) {
            for(int j = i; j < 1000; ++j) {
                if(is_val(i * j) && i * j > ans) ans = i * j;
            }
    
        }
        printf("%d\n", ans);
        return 0;
    }
    

    扩展:判断在base进制下是不是回文数的代码

    #include <stdio.h>
    
    int is_val(int n, int base) {
        int x = n;
        int temp = 0;
        while(x) {
            temp = temp * base + x % base;
            x /= base;
        }
        return temp == n;
    }
    
    int main() {
        int ans = 0;
        for(int i = 100; i < 1000; ++i) {
            for(int j = i; j < 1000; ++j) {
                if(is_val(i * j) && i * j > ans) ans = i * j;
            }
    
        }
        printf("%d\n", ans);
        return 0;
    }
    
    

    Problem05最小公倍数

    在这里插入图片描述
    就是找1~20的最小公倍数
    最小公倍数求解公式 lcm(a,b)=abgcd(a,b)lcm(a, b) = \frac{a * b}{gcd(a, b)}

    #include<stdio.h>
    
    int gcd(int a, int b) {
        return (b ? gcd(b, a % b) : a);
    }
    
    int main() {
        int ans = 1;
        for(int i = 2; i <= 20; ++i) {
        	//下面两行代码,求乘积找和下一个数的最小公倍数,乘积是下一个数的倍数时下一次循环
            if(ans % i == 0) continue;  
            ans *= i / gcd(ans, i);
        }
        printf("%d\n", ans);
        return 0;
    }
    
    

    Problem06平方和公式

    在这里插入图片描述

    平方和公式是一个比较常用公式,用于求连续自然数的平方和(Sum of squares),其和又可称为四角锥数,或金字塔数(square pyramidal number)也就是正方形数的级数。
    此公式是冯哈伯公式(Faulhaber’s formula)的一个特例

    在这里插入图片描述
    在这里插入图片描述

    扩展:

    • 立方和 :a3+b3=(a+b)(a2ab+b2)a^3 +b^3 = (a+b)(a^2-ab+b^2)
    • 立方差:a3b3=(ab)(a2+ab+b2)a^3 - b^3 = (a-b)(a^2+ab+b^2)
    • 立方和累加:13+23+...n3=[n(n+1)2]1^3 + 2 ^3 + ...n^3 =[\frac{n(n+1) }{2}]


    用三次方求平方,…

    #include<stdio.h>
    int main() {
        int sum1 = 5050, sum2 = 100 * (100 + 1) * (2 * 100 + 1) / 6;
        printf("%d\n", sum1 * sum1 - sum2);
        return 0;
    }
    
    

    Problem07线性筛

    在这里插入图片描述

    #include <stdio.h>
    #define max 200000 
    int prime[max + 5] = {0}; 
    void init() {
        for(int i = 2; i * i <= max; ++i) {
            if(prime[i]) continue;
            for(int j = i * i; j <= max; j += i) {
                prime[j] = 1;
            }
        }
        //将素数按从小到达顺序存起来,prime[0]记录素数个数
        //下面一个循环也可以写上面筛选的外层循环中, 但需要注意外层循环的条件
        //看下个代码    
        for(int i = 2; i <= max; ++i) {
            if(!prime[i]) prime[++prime[0]] = i;  
        }
    
        return ;
    }
    int main() {
        init();
        printf("%d\n", prime[10001]);
        return 0;
    }
    
    #include <stdio.h>
    #define maxn 200000
    int prime[maxn + 5] = {0};
    
    void init() {
        for(int i = 2; i <= maxn; ++i) {
            if(prime[i]) continue;
            prime[++prime[0]] = i; 
            
            //prime[0]++;
            //prime[prime[0]] = i;
    
            for(int j = i * 2; j <= maxn; j += i) {
                prime[j] = 1;
            }
        }
        return ;
    }
    
    int main() {
        init();
        printf("%d\n", prime[10001]);
        return 0;
    }
    

    线性筛代码

    #include <stdio.h>
    #define MAX 200000
    int prime[MAX + 5] = {0};
    
    void x_prime() {
        for(int i = 2; i <= MAX; ++i) {
            if(!prime[i]) prime[++prime[0]] = i;
            for(int j = 1; j <= prime[0]; ++j) {
                if(prime[j] * i > MAX) break;
                prime[prime[j] * i] = 1;
                if(i % prime[j] == 0) break; //判断当前素数是不是 j 中最小素数,是的话就跳出来
            }
        }
        return ;
    }
    
    int main() {
        x_prime();
        printf("%d\n", prime[10001]);
        return 0;
    }
    
    

    Problem08滑动窗口(逆运算) 长字符串输入

    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    • 逆运算: a与b通过法则一得到c, c与a,b任意一个通过法则二得到另一个,则法则二是法则一的逆运算,否则不是。如除法是乘法的逆运算而乘法不是出发的逆运算

    • 输入字符串的一个技巧
      从文件读入数据具体看欧拉复习

    #include <string.h>
    #include <stdio.h>
    #define max 1000
    
    char num[max + 5];
    int main() {
       int len = 0;
       while(~scanf("%s", num + len)) {
           len = strlen(num);
           printf("%s\n", num);    
       }
       return 0;
    }
    

    运行结果
    在这里插入图片描述

    利用滑动窗口法作此题
    8.h

    #ifndef _8_H
    #define _8_H
    char s[10010] = 
    "73167176531330624919225119674426574742355349194934\
    96983520312774506326239578318016984801869478851843\
    85861560789112949495459501737958331952853208805511\
    12540698747158523863050715693290963295227443043557\
    66896648950445244523161731856403098711121722383113\
    62229893423380308135336276614282806444486645238749\
    30358907296290491560440772390713810515859307960866\
    70172427121883998797908792274921901699720888093776\
    65727333001053367881220235421809751254540594752243\
    52584907711670556013604839586446706324415722155397\
    53697817977846174064955149290862569321978468622482\
    83972241375657056057490261407972968652414535100474\
    82166370484403199890008895243450658541227588666881\
    16427171479924442928230863465674813919123162824586\
    17866458359124566529476545682848912883142607690042\
    24219022671055626321111109370544217506941658960408\
    07198403850962455444362981230987879927244284909188\
    84580156166097919133875499200524063689912560717606\
    05886116467109405077541002256983155200055935729725\
    71636269561882670428252483600823257530420752963450";
    #endif
    

    8.cpp

    #include<cstdio>
    #include <cstring>
    #include<iostream>
    #include "8.h"
    using namespace std;
    
    int main() {
        long long MAX = 0, temp = 1, zero = 0;
    
        for(int i = 0; s[i]; i++) {
            if(i >= 13) {
                if(s[i - 13] == '0') {
                    zero--;
                } else {
                    temp /= (s[i - 13] - '0');
                }
            }
            if(s[i] == '0') {
                zero++;
            } else {
                temp *= (s[i] - '0');
            }
            if(zero == 0 && i >= 12 && temp > MAX) {
                MAX = temp;
            }
        }
        cout << MAX << endl;
        return 0;
    }
    
    

    Problem09素勾股数

    在这里插入图片描述
    素勾股数: a, b, c三者互质, a2+b2=c2a^2 + b^2 = c^2, 有四个性质

    1. (na, nb, nc)也是勾股数
    2. (a, b, c)之间两两互质
    3. a, b必为一奇一偶
    4. 任何素勾股数均可有如下表示(其中 n < m, gcd(n, m) = 1)​​​​​​​​​​​​​​​​​​​​​
      ​​​​​​​​​​​​​​​​​​​​​​​​​ a=2mna = 2 * m * n
      b=m2n2b = m^2 - n^2
      c=m2+n2c = m^2 + n^2

    代码:

    #include<iostream>
    using namespace std;
    
    int gcd(int a, int b) {
        return (b ? gcd(b, a % b) : a);
    }
    
    int main() {
        int ans = 0;
        for(int n = 1; n <= 33; ++n) {
            for(int m = n + 1; m * m + n * n < 1000; m++) {
                if(gcd(m, n) - 1) continue;
                int a = 2 * m *n;
                int b = m * m - n * n;
                int c = m * m + n * n;
                if(1000 % (a + b + c) == 0) {
                    int k = 1000 / (a + b + c);
                    ans = a * b * c * k * k * k;
                }
                if(ans) break;
            }
            if(ans) break;
        }
        cout << ans << endl;
        return 0;
    }
    
    

    Problem10素数和(线性筛)

    在这里插入图片描述
    线性筛写

    #include <stdio.h>
    #define max 2000000
    int a[max] = {0};
    
    void Prime() {
        for(int i = 2; i <= max; ++i) {
            if(!a[i]) {
                a[++a[0]] = i;
            }
            for(int j = 1; j <= a[0]; ++j) {
                if(a[j] * i > max) break;
                a[a[j] * i] = 1;
                if(i % a[j] == 0) break;
            }
        }
        
        return ;
    }
    
    int main() {
        Prime();
        long long ans = 0;
        for(int i = 1; i <= a[0]; ++i) {
            ans += a[i];
        }
        printf("%lld\n", ans);
        return 0;
    }
    
    

    Problem11方向数组

    方向数组
    在这里插入图片描述

    /************************
    重定向标准输入,将数据存入一个文件
    *************************/
    #include<iostream>
    using namespace std;
    
    int dirct[4][2] = {
        0, 1, 
        1, 0, 
        1, 1, 
        -1, 1
    };
    
    int arr[30][30] = {0};
    
    int main() {
        int ans = 0;
        for(int i = 5; i < 25; ++i) {
            for(int j = 5; j < 25; ++j) {
                cin >> arr[i][j];
            }
        }    
        
        for(int i = 5; i < 25; ++i) {
            for(int j = 5; j < 25; ++j) {
                for(int k = 0; k < 4; ++k) {
                    int temp = 1;
                    for(int l = 0; l < 4; ++l) {
                        int x = i + l * dirct[k][0];
                        int y = j + l * dirct[k][1];
                        temp *= arr[x][y];
                    }
                    if(temp > ans) ans = temp;
                }
            }
        }
        cout << ans << endl;
        return 0;
    }
    

    Problem12因子个数

    在这里插入图片描述
    关键点

    1. n=n= p1a1p_1 ^ {a_1} * p2a2p3a3...pnanp_2 ^ {a_2}*p_3^{a_3}...p_n^{a_n}
      则 n 的因子个数 f(n)=(a1+1)(a2+1)(a3+1)...(an+1)f(n) = (a_1 + 1) * (a_2 + 1) * (a_3 + 1)...(a_n + 1)
    2. 若A,B互质,则 f(AB)=f(A)f(B)f(A*B) = f(A) * f(B)

    本题两种做法:试除法 和 线性筛来做
    试除法在欧拉3求最大素因子时用到,从2开始除尽所有素因子

    用线性筛最关键的一点是什么?
    主要是第二点
    线性筛原理是用一个数乘以素数来筛合数, iprime[j]i * prime[j]为一个合数
    那么f(iprime[j])=f(i)f(prime[j])f(i * prime[j]) = f(i) * f(prime[j])
    因此在筛素数的过程中直接把因子个数再求出来

    注意一点:
    i % prime[j] !=0i\ \%\ prime[j]\ != 0时, iiprime[j]prime[j]互质, f(iprime[j])=f(i)f(prime[j])f(i * prime[j]) = f(i) * f(prime[j])
    当筛到 i % prime[j]==0i\ \%\ prime[j] == 0时,iiprime[j]prime[j]不互质f(iprime[j])=f(i)/(min_num[i]+1)(min_num[i]+2)f(i * prime[j]) = f(i) / (min\_num[i] + 1) * (min\_num[i] + 2)
    min_num[i]min\_num[i]表示i的最小质因子的次数,在求因子个数同时求min_num[i]min\_num[i]

    代码:

    #include <cinttypes>
    #include<iostream>
    using namespace std;
    
    #define MAX 1000000
    int64_t num[MAX] = {0}; //因子的个数
    int64_t prime[MAX] = {0}; //标记素数
    int64_t min_num[MAX] = {0}; //最小因子的个数
    
    
    int64_t triangle(int64_t n) {
        return n * (n - 1) / 2;
    }
    
    
    //线性筛做
    void init() {
        for(int i = 2; i <= MAX; ++i) {
            if(!prime[i]) {
                prime[++prime[0]] = i;
                num[i] = 2;
                min_num[i] = 1;
            }
            for(int j = 1; j <= prime[0]; ++j) {
                if(i * prime[j] > MAX) break;
                prime[prime[j] * i] = 1;
                if(i % prime[j]) {
                    num[prime[j] * i] = num[i] * num[prime[j]];
                    min_num[i * prime[j]] = 1;
                } else {
                    num[i * prime[j]] = num[i] / (min_num[i] + 1) * (min_num[i] + 2);
                    min_num[i * prime[j]] = min_num[i] + 1;
                    break;
                }
            }
        }
        return ;
    }
    
    
    /*
    //试除(和求最大因子原理一样)
    int64_t f(int64_t x) {
        int64_t n = 1;
        for(int64_t i = 2; i * i <= x; ++i) {
            if(x % i) continue;
            int cnt = 0;
            while(x % i == 0) {
                cnt++;
                x /= i;
            }
            n *= (cnt + 1);
        }
        if(x - 1) n *= 2;
        return n;
    }
    */
    
    
    int main() {
    /*
        for(int i = 1; i <= MAX; ++i) {
            num[i] = f(i);
        }
    */
    
        init();
        int64_t n = 2;
        while(1) {
            if(n % 2 == 1) {
               if (num[n] * num[(n - 1) >> 1] > 500) break;
            } else {
                if(num[n >> 1] * num[n - 1] > 500) break;
            }
            n++;
        }
        cout << triangle(n) << endl;
        return 0;
    }
    

    Problem13大整数加法 文件中输入

    Large sum
    Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
    计算出以下一百个50位数的和的前十位数字。

    37107287533902102798797998220837590246510135740250
    46376937677490009712648124896970078050417018260538
    74324986199524741059474233309513058123726617309629
    91942213363574161572522430563301811072406154908250
    23067588207539346171171980310421047513778063246676
    89261670696623633820136378418383684178734361726757
    28112879812849979408065481931592621691275889832738
    44274228917432520321923589422876796487670272189318
    47451445736001306439091167216856844588711603153276

    大整数

    #include<stdio.h>
    #define max 55
    #include <string.h>
    char str[max + 5] = {0};
    int ans[max + 5] = {0};
    //ans[0] 记录位数
    int main() {
        while(~scanf("%s", str)) {
            int len = strlen(str);
            if(len > ans[0]) ans[0] = len;
            for(int i = 0; i < len; ++i) {
                ans[len - i] += str[i] - '0';
            }
            //处理进位,等
            for(int i = 1; i <= ans[0]; ++i) {
                if(ans[i] < 10) continue;
                ans[i + 1] += ans[i] / 10;
                ans[i] %= 10;
                ans[0] += (i == ans[0]);
            }
        }
        for(int i = ans[0]; i > ans[0] - 10; i--) {
            printf("%d", ans[i]);
        }
        printf("\n");
        return 0;
    }
    
    

    扩展:求aba^b

    在这里插入图片描述

    HZOJ 54超级大整数
    在这里插入图片描述


    Problem14考拉兹序列 记忆化

    在这里插入图片描述
    记忆化

    #include <stdio.h>
    #define max 1000000
    #define size 1000000
    int keep[max + 5] = {0}; 
    
    typedef long long ll;
    
    
    ll getlen(ll n) {
        if(n == 1) return 1;
        if(n <= max && keep[n]) return keep[n]; 
        ll ret = 0;
        if(!(n & 1)) ret =  getlen(n >> 1) + 1;
        else ret = getlen(3 * n + 1) + 1;
        if(n <= size) keep[n] = ret;
        return ret;
    }
    
    
    
    int main() {
        ll ans = 0, len = 0;
        for(int i = 1; i < max; ++i) {
            ll temp = getlen(i); 
            if(temp > len) {
                ans = i;
                len = temp;
            }
    
        }
        printf("%lld %lld\n",  ans, len);
    
        return 0;
    }
    
    

    Problem15排列组合公式

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    #include <inttypes.h>
    #include <stdio.h>
    
    int main() {
        int64_t ans = 1, m = 20;
        for(int64_t i = 40; i >= 21; i--) {
            ans *= i;
            while(m && ans % m == 0) {
                ans /= m;
                m--;
            }
        }
        printf("%" PRId64 "\n", ans);
        return 0;
    }
    

    Problem16数字的幂 大整数

    在这里插入图片描述

    #include <iostream>
    using namespace std;
    #define MAX 1000000
    
    long long ans[MAX + 5] = {1, 1};
    
    int main() {
    	int n = 100;
    	long long sum = 0;
    	
    	while(n--) {
    		for(long long i = 1; i <= ans[0]; ++i) {
    			ans[i] *= 1024;
    		}
    		for(long long i = 1; i <= ans[0]; ++i) {
    			if(ans[i] < 10) continue;
    			ans[i + 1] += ans[i] / 10;
    			ans[i] %= 10;
    			ans[0] += (i == ans[0]);
    		}
    	}
    	
    	for(long long i = ans[0]; i >= 1; --i) {
    		sum += ans[i];
    	}
    	
    	cout << sum << endl;
    	return 0;
    } 
    

    Problem17英文字母个数

    在这里插入图片描述

    #include<stdio.h>
    int get_letters(int n) {
        static int arr1[20] = {
            0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3,
            6, 6, 8, 8, 7, 7, 9, 8, 8,
        };
        static int arr2[10] = {
            0, 0, 6, 6, 5, 5, 5, 7, 6, 6 
        };
        if(n < 20) {
            return arr1[n];
        } else if(n < 100) {
            return arr2[n / 10] + arr1[n % 10];
        } else if(n < 1000) {
            if(n % 100 == 0) {
                return arr1[n / 100] + 7;
            }
            return arr1[n / 100] + 10 + get_letters(n % 100);
        } else {
            return 11;
        }
    }
    int main() {
        int sum = 0;
        for(int i = 1; i <= 1000; ++i) {
            sum += get_letters(i);
        }
        printf("%d\n", sum);
        return 0;
    }
    
    

    Problem18记忆化 动态规划 dfs

    在这里插入图片描述
    加记忆化

    #include<iostream>
    using namespace std;
    
    #define MAX 20
    int val[MAX][MAX];
    
    int keep[MAX][MAX] = {0}; //记忆化
    
    int dfs(int i, int j, int n) {
        if(i + 1 == n) return val[i][j];
        if(keep[i][j]) return keep[i][j];
        int val1 = dfs(i + 1, j, n);
        int val2 = dfs(i + 1, j + 1, n);
        return keep[i][j] = (val1 > val2 ? val1 : val2) + val[i][j];
    
    }
    
    int main() {
        for(int i = 0; i < MAX; i++) {
            for(int j = 0; j <= i; j++) {
                cin >> val[i][j];
            }
        }    
        cout << dfs(0, 0, MAX) << endl;
        return 0;
    }
    
    

    动态规划

    #include<iostream>
    #include <algorithm>
    using namespace std;
    #define max 20
    int val[max][max] = {0};
    
    
    int main() {
        for(int i = 0; i < max; ++i) {
            for(int j = 0; j < i; ++j) {
                cin >> val[i][j];
            }
        }
        for(int i = max - 2; i >= 0; i--) {
            for(int j = 0;  j <= i; ++j) {
                val[i][j] += ( val[i + 1][j] > val[i + 1][j + 1] ? val[i + 1][j] : val[i + 1][j + 1]);
            }
        }
        cout << val[0][0] << endl;
        return 0;
    }
    
    

    Problem20阶乘数字和 大整数

    在这里插入图片描述

    #include<stdio.h>
    #define MAX 500
    
    int ans[MAX] = {1, 1, 0};
    
    int main() {
        int sum = 0;
        for(int i = 1; i <= 100; ++i) {
            for(int j = 1; j <= ans[0]; ++j) {
                ans[j] *= i;
            }
            for(int k = 1; k <= ans[0]; ++k) {
                if(ans[k] < 10) continue;
                ans[k + 1] += ans[k] / 10;
                ans[k] %= 10;
                ans[0] += (k == ans[0]);
            }
        }
        for(int i = 1; i <= ans[0]; ++i) {
            sum += ans[i];
        }
        printf("%d\n", sum);
        return 0;
    }
    
    

    Problem21因子和

    在这里插入图片描述


    Problem24 字典序全排列

    在这里插入图片描述

    #include<iostream>
    using namespace std;
    
    #define STATUS 1000000
    #define MAX_N  15
    int fac[MAX_N] = {0}; //存10个数的阶乘;
    int num[MAX_N] = {0}; //存10个数是否用过
    //求阶乘
    void init() {
        fac[0] = 1;
        num[0] = 1;
        for(int i = 1; i <= 10; ++i) {
            fac[i] = i * fac[i - 1];
            num[i] = 1;
        }
        return ;
    }
    
    
    //返回两个数,一个是当前数x从零跳到几在主函数中输出
    //另一个返回还需跳几个状态n
    int get_num(int n, int fac, int &x) {
        int step = n / fac;
        int j = 0;
        
        //让x从第一个没用过的数开始跳
        while(!num[j]) j++;
        x = j;
        
        while(step) {
            if(num[x + 1]) {
                x++;
                step--;
            } else {
                x++;
            }
        }
    
        num[x] = 0;
        n %= fac;
        return n;
    }
    
    int main() {
        init();
        int n = 250 - 1; //当前需要跳得次数
        for(int i = 10; i >= 1; i--) {
            int x;
            n = get_num(n, fac[i - 1], x);
            cout << x;
        }
        cout << endl;
        return 0;
    }
    

    字典序全排列函数

    #include <algorithm>
    #include<iostream>
    using namespace std;
    int main() {
        int num[10];
        for(int i = 0; i < 10; ++i) num[i] = i;
        int k = 1000000 - 1;
        do {
            next_permutation(num, num + 10);
            k--;
        } while(k);
        for(int i = 0; i < 10; ++i) {
            cout << num[i];
        }
        cout << endl;
        return 0;
    }
    
    

    Problem25大整数斐波那契 滚动数组

    在这里插入图片描述

    #include<stdio.h>
    #include <math.h>
    int f[3][1005];
    
    int main() {
        int n = 2;
        //f[1] = 1, f[2] = 1;
        f[1][0] = 1;
        f[1][1] = 1;
        f[2][0] = 1;
        f[2][1] = 1;
        while(f[n % 3][0] < 1000){
            n += 1;
            int *a = f[n % 3], *b = f[(n - 1) % 3], *c = f[(n - 2) % 3];
            for(int i = 1; i <= b[0]; ++i) {
                a[i] = b[i] + c[i];
            }
            a[0] = b[0];
            for(int i = 1; i <= a[0]; ++i) {
                if(a[i] < 10) continue;
                a[i + 1] += a[i] / 10;
                a[i] %= 10;
                a[0] += (i == a[0]);
            }
            //f[n % 3] = f[(n - 1) % 3] + f[(n - 2) % 3];
            //printf("%d\n", f[n % 3]);
        }
        printf("%d\n", n);
        return 0;
    }
    
    #include <stdio.h>
    int main() {
        int fib[3][1005] = {0};
        fib[0][0] = fib[0][1] = 1;
        fib[1][0] = fib[1][1] = 1;
        int n = 1;
        while(fib[n % 3][0] < 1000) {
            n++;
            for(int i = 1; i <= fib[(n - 1) % 3][0]; ++i) {
                fib[n % 3][i] = fib[(n - 1) % 3][i] + fib[(n - 2) % 3][i];
            }
            fib[n % 3][0] = fib[(n - 1) % 3][0];
            for(int i = 1; i <= fib[n % 3][0]; i++) {
                if(fib[n % 3][i] < 10) continue;
                fib[n % 3][i + 1] += fib[n % 3][i] / 10;
                fib[n % 3][i] %= 10;
                fib[n % 3][0] += (i == fib[n % 3][0]);
            }
        }
        printf("%d\n", n + 1);
        
        return 0;
    }
    
    

    Problem26求循环节

    在这里插入图片描述
    列竖式计算可以看到每次余数都乘10,当余数在之前出现过时就开始出现循环节
    1/n 竖式计算时余数有n种(0 – n-1)其中余数是0时就除尽了,因此循环节最长为n-1;

    #include <cstring>
    #include <iostream>
    using namespace std;
    #define MAX 1000
    
    int rest[MAX]; //记录最初出现的位置,若是0表示没出现
    
    int get_maxlen(int n) {
        memset(rest, 0, sizeof(rest));
        int r = 10 % n, index = 1; 
        while(r && !rest[r]) {
            rest[r] = index++;    //index同时记录位置和长度
            r *= 10;
            r %= n;
        }
        return r ? index - rest[r] :0;
    }
    
    int main() {
        int num, len, MAXLEN = 0;
        for(int i = 2; i <= MAX; ++i) {
            len = get_maxlen(i);
            if(len > MAXLEN) num = i, MAXLEN = len; 
        }
        cout << num << endl;
        return 0;
    }
    
    
    

    Problem28规律 螺旋数阵对角线

    在这里插入图片描述
    思路: 找每圈的四个角的规律

    #include<stdio.h>
    int main() {
        int sum = 1;
        for(int l = 3; l <= 1001; l += 2) {
            sum += 4 * l * l - 6 * l + 6;
        }
        
        printf("%d\n", sum);
        return 0;
    }
    
    

    发现 sum=4(32+52+72+...+10012)6(3+5+7+..)+Csum = 4*(3^2 + 5^2 + 7^2 +...+ 1001^2) - 6*(3 + 5 + 7 +.. ) + C
    可推倒出一个公式


    Problem29 大整数去重

    在这里插入图片描述

    #include <algorithm>
    #include <cstring>
    #include<iostream>
    #include <cstdlib>
    using namespace std;
    #define maxn 10000
    #define maxm 210
    int *result[maxn + 5];
    int result_len = 0;
    
    int find_result(int *num) {
        for(int i = 0; i < result_len; ++i) {
            if(memcmp(result[i], num, sizeof(int) * maxm) == 0) {
                return i + 1;
            }
        }
        return 0;
    }
    
    
    int *calc(int a, int b) {
        int *temp = (int *)calloc(sizeof(int), maxm);
        temp[0] = 1, temp[1] = 1;
        for(int i = 0; i < b; ++i) {
            for(int j = 1; j <= temp[0]; j++) temp[j] *= a;
            for(int j = 1; j <= temp[0]; ++j) {
                if(temp[j] < 10) continue;
                temp[j + 1] += temp[j] / 10;
                temp[j] %= 10;
                temp[0] += (j == temp[0]);
            }
        }
        return temp;
    }
    
    
    
    int main() {
        for(int a = 2; a <= 100; ++a) {
            for(int b = 2; b <= 100; ++b) {
                int *temp = calc(a, b);
                if(find_result(temp) == 0) {
                    result[result_len++] = temp;   
                }
            }
        }
        cout << result_len << endl;
        return 0;
    }
    
    

    Problem30各位数字的5次幂

    在这里插入图片描述

    #include <stdio.h>
    #include <math.h>
    #define maxn  3554294
    int is_val(int n) {
        int x = n, temp = 0;
        while(x) {
            temp += (int)pow(x % 10, 5);
            x /= 10;
        }
        return temp == n;
    }
    
    int main() {
        int sum = 0;
        for(int i = 2; i <= maxn; ++i) {
            if(is_val(i)) sum += i;
        }
        printf("%d\n", sum);
        return 0;
    }
    
    

    Problem31硬币求和 递推★★★

    在这里插入图片描述
    最笨的递归写法

    #include<iostream>
    using namespace std;
    int w[10] = {0, 1, 2, 5, 10, 20, 50, 100, 200};
    int keep[10][210];
    int f(int k, int n) {
        if(n == 0) return 1;
        if(n < 0) return 0;
        if(k == 1) return 1;
        return f(k - 1, n) + f(k, n - w[k]);    
    }
    
    
    int main() {
        cout << f(8, 200) << endl;
        return 0;
    }
    

    Problem32求数字位数

    在这里插入图片描述

    1. 求数字的位数 floor(log10(n))+1floor(log10(n)) + 1, 求出 i,j,iji, j, i * j 的位数和筛去不是九的
    2. 针对每组 i,ji, j 依次把 i,j,iji, j, i * j各个位标记有重复时不符合条件
    #include<cmath>
    #include<iostream>
    #include <cstring>
    using namespace std;
    int num[15];
    int digit(int i, int j) {
        int sum_digit = 0;
        sum_digit += (int)floor(log10(i)) + 1;
        sum_digit += (int)floor(log10(j)) + 1;
        sum_digit += (int)floor(log10(i * j)) + 1;
        return sum_digit;
    }
    
    int is_val(int n) {
        while(n) {
            if(n % 10 == 0) return 0;
            if(num[n % 10]) return 0;
            num[n % 10] = 1;
            n /= 10;
        }
        return 1;
    }
    
    int is_ok(int i, int j) {
        memset(num, 0, sizeof(num));
        if(is_val(i) && is_val(j) && is_val(i * j)) return 1;
        return 0;
    }
    
    int main() {
        int arr[100000] = {0};
        long long sum = 0;
        for(int i = 1; i <= 100; i++) {
            for(int j = i + 1; ; ++j) {
                int digs = digit(i, j);
                if(digs < 9) continue;
                else if(digs > 9) break;
                if(is_ok(i, j) && !arr[i * j]) sum += i * j, arr[i * j] = 1;
            }
        }
        cout << sum << endl;
        return 0;
    }
    
    

    Problem33错误约分正确答案

    在这里插入图片描述
    判断两个分数是否相等转化为乘法

    #include<stdio.h>
    
    int gcd(int a, int b) {
        return (b ? gcd(b, a % b) : a);
    }
    
    int is_val(int x, int y) {
        int x1 = x / 10, x2 = x % 10;
        int y1 = y / 10, y2 = y % 10;
        if(!x2 || !y2) return 0;
        if(x1 == y1 && x2 * y == x * y2) return 1;
        if(x1 == y2 && x2 * y == x * y1) return 1;
        if(x2 == y1 && x1 * y == x * y2) return 1;
        if(x2 == y2 && x1 * y == x * y1) return 1;
    }
    
    int main() {
        int  x = 1, y = 1, c = 1;
        for(int a = 10; a < 100; ++a) {
            for(int b = a + 1; b < 100; b++) {
                if((!is_val(a, b))) continue;
                x *= a, y *= b;
                c = gcd(x, y);
                x /= c, y /= c;
            }
        }
        printf("%d\n", y);
        return 0;
    }
    
    

    Problem34各位数字的阶乘和 记忆化

    在这里插入图片描述

    #include <stdio.h>
    #define maxn 2903040
    
    int k[10] = {1,1};
    int f(int n) {
        if(k[n]) return k[n]; //记忆化
        return k[n] = f(n - 1) * n;
    }
    
    int is_val(int n) {
        int x = n, sum = 0;
        while(x) {
            sum += f(x % 10);
            x /= 10;
        }
        return sum == n;
    }
    int main() {
        int sum = 0;
        for(int i = 3; i <= maxn; ++i) {
            if(is_val(i)) sum += i;
        }
        printf("%d\n", sum);
        return 0;
    }
    

    Problem35圆环素数 位数

    在这里插入图片描述

    #include <cmath>
    #include<iostream>
    using namespace std;
    
    #define MAX 1000000
    int prime[MAX], is_prime[MAX];
    void init() {
        for(int i = 2; i <= MAX; ++i) {
            if(!is_prime[i]) prime[++prime[0]] = i;
            for(int j = 1; j <= prime[0]; ++j) {
                if(i * prime[j] > MAX) break;
                is_prime[i * prime[j]] = 1;
                if(i % prime[j] == 0) break;
            }
        }
        return ;
    }
    
    int is_val(int n) {
        if(is_prime[n]) return 0;
        int digit = floor(log10(n)) + 1;
        int temp = pow(10, digit - 1);
        for(int i = 1; i < digit; ++i) {
            int t;
            t = n % temp;
            t = t * 10 + n / temp;
            if(is_prime[t]) return 0;
            n = t;
        }
        return 1;
    }
    
    int main() {
        init();
        int sum = 0;
        for(int i = 2; i <= MAX; ++i) {
            if(is_val(i)) sum++;
        }
        cout << sum << endl;
        return 0;
    }
    

    Problem36双进制下回文数

    在这里插入图片描述

    #include <stdio.h>
    #define maxn 1000000
    
    
    //判断base进制下是不是回文数
    int is_val(int n, int base) {
        int m = n, sum = 0;
        while(m) {
            sum = sum * base +  m % base;
            m /= base;
        }
        return sum == n;
    }
    
    
    
    int main() {
        int sum = 0;
        for(int i = 1; i <= maxn; ++i) {
            if(is_val(i, 10) && is_val(i, 2)) sum += i;
        }
        printf("%d\n", sum);
        return 0;
    }
    
    

    Problem37左截右截依旧是素数

    在这里插入图片描述

    #include <math.h>
    #include<stdio.h>
    #define MAX 1000000
    int prime[MAX] = {0};
    int is_prime[MAX] = {1, 1, 0};
    
    
    void init() {
        for(int i = 2; i <= MAX; ++i) {
            if(!is_prime[i]) prime[++prime[0]] = i;
            for(int j = 1; j <= prime[0]; ++j) {
                if(prime[j] * i > MAX) break;
                is_prime[prime[j] * i] = 1;
                if(i % prime[j] == 0) break;
            }
        }
        return ;
    }
    
    
    int is_val(int n) {
        int digit = floor(log10(n)) + 1;    //存位数
        int h = pow(10, digit - 1);
        int tmp = n;
    
        /*
        //从右截
        for (int i = 0;i <  digit - 1 ;i++) {
            tmp /= 10;
            if(is_prime[tmp]) return 0;
        }
        //从左截
        tmp = n;
        for (int i = 0;i < digit - 1;i++) {
            tmp %= h;
            if(is_prime[tmp]) return 0;
            h /= 10;
        }
        */
        
    
    
        //从右往左截
        while(tmp / 10) {
            tmp /= 10;
            if(is_prime[tmp]) return 0;
        }
        //从左截
        int temp2 = n;
        while(temp2 > 10) {
            int digit1 = floor(log10(temp2)) + 1;
            int h = pow(10, digit1 - 1);
            if(is_prime[temp2 % h]) return 0;
            temp2 %= h; 
        }
        return 1;
    }
    
    int main() {
        init();
        int sum = 0;
        int flag = 11;
        for(int i = 1; i <= prime[0] && flag; ++i) {
            if(prime[i] < 10) continue;
            if(is_val(prime[i])) { 
                sum += prime[i];
                flag--; 
            }   
        }
        printf("%d\n", sum);
        return 0;
    }
    

    Problem38连接几个乘积为 全数字判断

    在这里插入图片描述

    #include<stdio.h>
    #include<math.h>
    
    int digits(long long n) {
        if(!n) return 1;
        return floor(log10(n)) + 1;
    }
    
    long long calc(int x) {
        long long n = 1, ans = 0;
        while(digits(ans) < 9) {
            ans *= pow(10, digits(x * n));
            ans += n * x;
            n += 1;
        }
        if(digits(ans) - 9) return 0;
        int num[10] = {1, 0}; //标记数组
        int temp = ans;
        while(temp) {
            if(num[temp % 10]) return 0;
            num[temp % 10] += 1;
            temp /= 10;
        }
        return ans;
    }
    
    int main() {
        long long ans = 0;
        for(int i = 1; i < 10000; ++i) {
            int tmp = calc(i);
            if(tmp > ans) ans = tmp;
        }
        printf("%lld\n", ans);
        return 0;
    }
    

    Problem39素勾股数的使用

    在这里插入图片描述
    找出素勾股数再求出他们的倍数

    #include<iostream>
    using namespace std;
    
    #define maxn 1000
    int cnt[maxn + 5] = {0};
    
    
    int gcd(int a, int b) {
        return (b ? gcd(b, a % b) : a);
    }
    
    int main() {
        for(int n = 1; n <= 32; ++n) {
            for(int m = n + 1; m <= 32; m++) {
                if(gcd(m, n) - 1) continue;
                int a = m * m - n * n;
                int b = 2 * m * n;
                int c = m * m + n * n;
                for(int p = a + b + c; p <= 1000; p += (a + b + c)) {
                    cnt[p] += 1;
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= maxn; i++){
            if(cnt[i] > cnt[ans]) ans = i;
        }
        cout << ans << endl;
        return 0;
    }
    
    

    Problem44二分查找 五边形数

    在这里插入图片描述

    1. 判断是不是五边形数用二分法,二分函数而不是二分数组

    2. 确定边界

    思路
    p(j)p(j)表示五边形数,D表示差

    • 从2往后枚举jj从第n项往前找五边形数再看他们与 p(j)p(j) 的和与差是不是都是五边形数,当p(j)p(j)p(j1)p(j - 1)的差都大于D就不用再找了因为差只会越来越大

    • 设个变量kk,从j1j - 1开始一点点减小只要p(j)p(k)<Dp(j) - p(k) < D 就有可能找到更小的差,循环内再判断p(j)+p(k)p(j) + p(k)p(j)p(k)p(j) - p(k) 是不是五边形数

    因为是递增函数所以用二分来做,比如判断15是不是五边形数那么就在 1p(15)1 - p(15)区间内用二分来找

    #include <cinttypes>
    #include<iostream>
    using namespace std;
    
    inline int64_t Pentagonal(int64_t n) {
        return n * (3 * n - 1) / 2;
    }
    
    int is_pentagonal(int64_t p) {
        int head = 1, tail = p;
        int mid;
        while(head <= tail) {
            mid = (head + tail) >> 1;
            if(Pentagonal(mid) == p) return 1;
            else if(Pentagonal(mid) > p) {
                tail = mid - 1;
            } else {
                head = mid + 1;
            }
        }
        return 0;
    }
    
    int main() {
        int64_t j = 2, D = INT64_MAX;
        
        while(Pentagonal(j) - Pentagonal(j - 1) < D) {
            int64_t k = j - 1;
            while(Pentagonal(j) - Pentagonal(k) < D) {
                if(is_pentagonal(Pentagonal(j) + Pentagonal(k)) && is_pentagonal(Pentagonal(j) - Pentagonal(k))) {
                    D = Pentagonal(j) - Pentagonal(k);
                    cout << k << " " << j << " " << D << endl;
                }
                k--;
                if(!k) break;
            }
            j++;
        }
        cout << D << endl;
        return 0;
    }
    
    #include<stdio.h>
    long long  Pentagonal(long long n) {
        return  n * (3 * n - 1) / 2;
    }
    
    long long binary_search(long long (*func)(long long), long long n, long long x) {
        long long head = 1, tail = n, mid;
        while(head <= tail) {
            mid = (head + tail) >> 1;
            if(func(mid) == x) return mid;
            if(func(mid) < x) head = mid + 1;
            else tail = mid - 1;
        }
        return 0;
    }
    
    int main() {
        long long n = 2, D = INT32_MAX, pk, pj;
        while(Pentagonal(n) - Pentagonal(n - 1) < D) {
            pk = Pentagonal(n);
            for(long long j = n - 1; j >= 1; j--) {
                pj =  Pentagonal(j);
                if(pk - pj >= D) break;
                long long ind1, ind2;
                ind1 = binary_search(Pentagonal, 2 * n,  pk + pj);
                if(ind1) {
                    ind2 = binary_search(Pentagonal, n, pk - pj);
                    if(ind2) D = pk - pj;
                }
            }
            n++;
        }
        printf("%lld\n", D);
        return 0;
    }
    
    

    Problem45六边形数中 二分查找 五边形数

    在这里插入图片描述
    六边形中找五边形

    #include<stdio.h>
    
    typedef long long int1;
    
    int1 Triangle(int1 n) {
        return n * (n + 1) / 2;
    }
    
    int1 Pentangle(int1 n) {
        return n * (3 * n - 1) / 2;
    }
    
    int1 Hexangonal(int1 n) {
        return n * (2 * n - 1);
    }
    
    int1 binary_search(int1 (*num)(int1), int1 n, int1 x) {
        int1 head = 0, tail = n - 1, mid;
        while(head <= tail) {
            mid = (head + tail) >> 1;
            if(num(mid) == x) return mid;
            if(num(mid) < x) head = mid + 1;
            else tail = mid - 1;
        }
        return -1;
    }
    
    int main() {
        int1 n = 144;
        while(binary_search(Pentangle, 2 * n, Hexangonal(n)) == -1) n += 1;
        printf("%d\n", Hexangonal(n));
        return 0;
    }
    
    

    Problem46不一定奇合数=素数+平方2倍

    在这里插入图片描述

    #include<iostream>
    using namespace std;
    
    #define maxn 1000000
    int prime[maxn + 5] = {0};
    int is_prime[maxn + 5] = {0};
    
    int is_sqrt(int n) {
        return 2 * n * n;
    }
    
    
    void init() {
        for(int i = 2; i <= maxn; ++i) {
            if(!is_prime[i]) prime[++prime[0]] = i;
            for(int j = 1; j <= prime[0]; ++j) {
                if(i * prime[j] > maxn) break;
                is_prime[i * prime[j]] = 1;
                if(i % prime[j] == 0) break;
            }
        }
        return ;
    }
    
    
    bool binary_search(int(*func)(int), int l, int r, int x) {
        if(l > r) return false;
        int mid = (l  + r) >> 1;
        if(func(mid) == x) return true;
        if(func(mid) < x) l = mid + 1;
        else r = mid - 1;
        return binary_search(func, l, r, x);
    }
    
    bool check(int n) {
        for(int j = 1; j <= prime[0] && prime[j] < n; j++) {
            if(binary_search(is_sqrt, 1, n - prime[j], n - prime[j])) return true;
        }
        return false;
    }
    
    int main() {
        init();
        int ans = 0;
        for(int i = 9; i <= maxn; i += 2) {
            if(!is_prime[i]) continue;
            if(check(i)) continue;
            ans = i;
            break;
        }
        cout << ans << endl;
        return 0;
    }
    

    Problem47素因子种类

    在这里插入图片描述
    用线性筛,筛素数的同时用一个数组存素因子种类个数,素数就一个素因子

    #include<iostream>
    using namespace std;
    #define MAX 1000000
    
    int prime[MAX], cnt[MAX];
    void init() {
        for(int i = 2; i <= MAX; ++i) {
            if(!prime[i]) {
                prime[++prime[0]] = i;
                cnt[i] = 1;
            }
            for(int j = 1; j <= prime[0]; ++j) {
                if(i * prime[j] > MAX) break;
                prime[i * prime[j]] = 1;
                if(i % prime[j] == 0) {
                    cnt[i * prime[j]] = cnt[i];
                } else {
                    cnt[i * prime[j]] = cnt[i] + 1;
                }
            }
        }
        return ;
    }
    int main() {
        init();
        for(int i = 2; ;i++) {
            if(cnt[i] != 4) continue;
            if(cnt[i] != cnt[i + 1]) continue;
            if(cnt[i + 1] != cnt[i + 2]) continue;
            if(cnt[i + 2] != cnt[i + 3]) continue;
            cout << i << endl;
            break;
        }
        return 0;
    }
    
    
    展开全文
  • 欧拉计划 该存储库包含有关的练习的解决方案。 问题
  • 欧拉计划-汇总

    千次阅读 2019-01-23 22:24:03
    这个拿来写欧拉计划吧 主要是我算法写得太烂了。就酱。

    这个拿来写欧拉计划吧
    中文网:https://pe-cn.github.io/
    原网址:https://projecteuler.net/
    主要是我算法写得太烂了。Hahaha。

    一周写1-2个的样子,(我怀疑后面可能一个都写不动。)
    最后可能还得去偷看别人的算法,上次一个老师跟我说,你看到一个算法,就学一个算法好了。
    那好吧。

    先从完成人数多的开始写吧。
    在这里插入图片描述

    欧拉计划:
    (按照难度写。。太难我不会)
    [19.1.23]-1.约数问题
    [19.1.24]-2.斐波拉契偶数求和

    [19.1.28]-
    6.最大质因数

    展开全文
  • 项目欧拉 欧拉计划问题的解决方案 这是我尝试解决Python和R中的Project Euler编码问题的尝试。
  • JS实现欧拉计划

    2020-03-17 18:52:58
    Project Euler - 欧拉计划第一题 3的倍数和5的倍数第二题 偶斐波那契数持续更新中... 第一题 3的倍数和5的倍数 如果我们列出10以内所有3或5的倍数,我们将得到3、5、6和9,这些数的和是23。求1000以内所有3或5的...

    欧拉计划是一系列有挑战性的数学与计算机编程题;要解开它们,需要的不止是数学知识:尽管数学能够帮助你找到一些优雅而有效的方法,大多数题目仍需要借助计算机和编程技巧来完成解答。

    第一题 3的倍数和5的倍数

    如果我们列出10以内所有3或5的倍数,我们将得到3、5、6和9,这些数的和是23。求1000以内所有3或5的倍数的和。

    /*js实现代码过程*/
    	  var num = [];
          var sum = 0;
          for (var i = 0; i < 1000; i++) {
            if (i % 3 === 0 || i % 5 === 0) {
              num.push(i);
            }
          }
          for (var j = 0; j < num.length; j++) {
            sum += num[j];
          }
          console.log(num);
          console.log(sum);
    

    输出为

    Array(467) [ 0, 3, 5, 6, 9, 10, 12, 15, 18, 20, … ]
    233168


    第二题 偶斐波那契数

    斐波那契数列中的每一项都是前两项的和。
    由1和2开始生成的斐波那契数列前10项为:1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
    考虑该斐波那契数列其值不超过四百万的项,求其中为偶数的项之和。

     	 var sum = 0;
         var arr = [1, 2];
         var i = 0;
         while (true) {
           arr[i + 2] = arr[i] + arr[i + 1];
           if (arr[i + 2] > 4000000) {
             break;
           }
           i++;
         }
         var e_arr = [];
         for (var j = 0; j < arr.length - 1; j++) {
           if (arr[j] % 2 === 0) {
             sum += arr[j];
             e_arr.push(arr[j]);
           }
         }
         console.log(arr);
         console.log(e_arr);
         console.log(sum);
    

    输出为

    Array(33) [ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … ]
    Array(11) [ 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, … ]
    4613732


    第三题 最大质因数

    13195的所有质因数为5、7、13和29。
    600851475143最大的质因数是多少?
    分析:
    如果不优化代码,求解的时间会很长。
    首先600851475143不是一个偶数,所以在取因数的时候完全可以从3开始,只取奇因数;
    其次先算一算600851475143的最小最大因数。

    var number = 600851475143;
    for (var i = 3; i < number; i += 2) {
      if (number % i === 0) {
        console.log(i, number / i);
        break;
      }
    }
    

    输出为

    71 , 8462696833
    [Done] exited with code=0 in 0.179 seconds

    这样就大大的减少计算量,再求解

    //首先求出number的所有奇因数
    var max = 8462696833;
    var arr = [];
    for (var i = 3; i < max; i += 2) {
      if (max % i === 0) {
        arr.push(i);
      }
    }
    //再取出奇因数中所有的质数
    var even = [];
    for (var j = 0; j < arr.length; j++) {
      var flag = true;
    //用开平方根和break也能提高性能
      for (var k = 2; k < Math.sqrt(arr[j]); k++) {
        if (arr[j] % k === 0) {
          flag = false;
          break;
        }
      }
      if (flag) {
        even.push(arr[j]);
      }
    }
    //取出even数组中最后一个元素
    console.log(even[even.length - 1]);
    

    输出为

    6857
    [Done] exited with code=0 in 39.833 seconds

    最后还是花费了40秒,先这样吧。。


    第四题 最大回文乘积

    回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。
    找出由两个3位数相乘得到的最大回文乘积。
    分析:首先,9009的个位和千位一样,十位和百位一样。所以判断是不是回文数,就判断它每位是不是一致的。其次,999*999=998001,所以三位相乘最多获取六位数。下面就可以写代码了

    var res = [];
    for (var i = 100; i < 1000; i++) {
      for (var j = 100; j < 1000; j++) {
        var num = i * j;
        var str = num.toString();
        var arr = str.split("");
        if (arr.length === 6) {
          if (arr[0] === arr[5] && arr[1] === arr[4] && arr[2] === arr[3]) {
            res.push(num);
          }
        }
      }
    }
    //将数组降序排列,得到最大值
    res.sort(function(a, b) {
      return b - a;
    });
    console.log(res[0]);
    

    输出为

    906609
    [Done] exited with code=0 in 0.471 seconds

    PS: 刚看了 apply() 方法,真是方便啊,最后根本不需要使用 sort()方法。将最后的代码改成

    //使用Math中的 max() 方法,得到最大值
    //第一个参数是this指向;第二个参数是数组
    var max = Math.max.apply(Math,res);
    console.log(max);
    

    第五题 最小倍数

    2520是最小的能够被1到10整除的数。
    最小的能够被1到20整除的正数是多少?
    分析:
    首先我们从2开始连乘到10,1x2x3都没问题;
    等到x4的时候,可以发现在1x2x3中有一个2,4/2=2所以只需要 x2就够了不需要*4;现在的连乘数列是 1x2x3x2。
    x5也没问题;于是数列变成了 1x2x3x2x5
    x6的时候发现在数列中有一个 2x3=6,所以不需要6;
    x7的时候,数列变成了 1x2x3x2x5x7
    x8的时候,发现数列中有 2x2=4,还缺少一个2
    x9时,数列中只有一个 3,还缺少一个3
    x10时,数列中已经有 2x5了
    所有我们可以得到 1x2x3x2x5x7x2x3 =2520
    也可以看出这其实就是找1-10的因数的过程,如果有因数就相除得到商
    分析完毕,下面是编程过程…

    var arr = [2];
    //从 2开始连乘到 20
    for (var i = 3; i <= 20; i++) {
      var index = 0;
      var res = i;
      for (var j = 0; j < arr.length; j++) {
        //判断 i有没有的因数,如果有就除以得到商,一直有一直除,最后就是 1了
        if (i % arr[j] == 0) {
          index++;
          res /= arr[j];
          if (res <= 1) {
            res = 1;
          }
        }
      }
      //如果 i没有因数,直接添加到数组中
      if (index == 0) {
        arr.push(i);
      } else {
        //如果 i有因数,就把最后的商添加到数组中
        arr.push(res);
      }
    }
    console.log(arr);
    var num = 1;
    //数组连乘就是最小的倍数
    for (var k = 0; k < arr.length; k++) {
      num *= arr[k];
    }
    console.log(num);
    

    输出为

    数组为: [
    2, 3, 2, 5, 1, 7, 2,
    3, 1, 11, 1, 13, 1, 1,
    2, 17, 1, 19, 1
    ]
    最小倍数为: 232792560
    [Done] exited with code=0 in 0.219 seconds


    第六题 平方的和与和的平方之差

    前十个自然数的平方的和是:
    12+ 22 + … + 102 = 385
    前十个自然数的和的平方是:
    (1 + 2 + … + 10)2 = 552 = 3025
    因此前十个自然数的平方的和与和的平方之差是 3025 − 385 = 2640。
    求前一百个自然数的平方的和与和的平方之差。

    var squares = 0;
    var sum = 0;
    for (var i = 1; i <= 100; i++) {
      sum += i * i;
      squares += i;
    }
    console.log("平方和:" + sum, ",", "和的平方:" + squares * squares);
    console.log("差:", squares * squares - sum);
    

    输出为

    平方和:338350 , 和的平方:25502500
    差: 25164150
    [Done] exited with code=0 in 0.154 seconds


    第七题 第10001个素数

    列出前6个素数,它们分别是2、3、5、7、11和13。我们可以看出,第6个素数是13。
    第10,001个素数是多少?

    var i = 2;
    var index = 0;
    while (true) {
      var flag = true;
      for (let j = 2; j < i; j++) {
        if (i % j === 0) {
          flag = false;
          break;
        }
      }
      if (flag) {
        index++;
      }
      i++;
      //当第10001个素数时,打印此时的值,但是别忘记-1,
      //同时退出循环
      if (index === 10001) {
        console.log(i - 1);
        break;
      }
    }
    

    输出为

    104743
    [Done] exited with code=0 in 2.453 seconds


    第八题 连续数字最大乘积

    在下面这个1000位正整数中,连续4个数字的最大乘积是 9 × 9 × 8 × 9 = 5832。

    73167176531330624919225119674426574742355349194934
    96983520312774506326239578318016984801869478851843
    85861560789112949495459501737958331952853208805511
    12540698747158523863050715693290963295227443043557
    66896648950445244523161731856403098711121722383113
    62229893423380308135336276614282806444486645238749
    30358907296290491560440772390713810515859307960866
    70172427121883998797908792274921901699720888093776
    65727333001053367881220235421809751254540594752243
    52584907711670556013604839586446706324415722155397
    53697817977846174064955149290862569321978468622482
    83972241375657056057490261407972968652414535100474
    82166370484403199890008895243450658541227588666881
    16427171479924442928230863465674813919123162824586
    17866458359124566529476545682848912883142607690042
    24219022671055626321111109370544217506941658960408
    07198403850962455444362981230987879927244284909188
    84580156166097919133875499200524063689912560717606
    05886116467109405077541002256983155200055935729725
    71636269561882670428252483600823257530420752963450

    找出这个1000位正整数中乘积最大的连续13个数字。它们的乘积是多少?

    var str =
     "73167176531330624919225119674426574742355349194934"
    +"96983520312774506326239578318016984801869478851843"
    +"85861560789112949495459501737958331952853208805511"
    +"12540698747158523863050715693290963295227443043557"
    +"66896648950445244523161731856403098711121722383113"
    +"62229893423380308135336276614282806444486645238749"
    +"30358907296290491560440772390713810515859307960866"
    +"70172427121883998797908792274921901699720888093776"
    +"65727333001053367881220235421809751254540594752243"
    +"52584907711670556013604839586446706324415722155397"
    +"53697817977846174064955149290862569321978468622482"
    +"83972241375657056057490261407972968652414535100474"
    +"82166370484403199890008895243450658541227588666881"
    +"16427171479924442928230863465674813919123162824586"
    +"17866458359124566529476545682848912883142607690042"
    +"24219022671055626321111109370544217506941658960408"
    +"07198403850962455444362981230987879927244284909188"
    +"84580156166097919133875499200524063689912560717606"
    +"05886116467109405077541002256983155200055935729725"
    +"71636269561882670428252483600823257530420752963450";
    
    var arr = str.split("");
    var arr1 = arr.map(function(value) {
      return parseInt(value);
    });
    var mul = [];
    for (var i = 0; i < arr1.length; i++) {
      if (arr1[i] == 0) {
        continue;
      }
      var num =
        arr1[i] *
        arr1[i + 1] *
        arr1[i + 2] *
        arr1[i + 3] *
        arr1[i + 4] *
        arr1[i + 5] *
        arr1[i + 6] *
        arr1[i + 7] *
        arr1[i + 8] *
        arr1[i + 9] *
        arr1[i + 10] *
        arr1[i + 11] *
        arr1[i + 12];
      mul.push(num);
      if (i === arr1.length - 13) {
        break;
      }
    }
    mul.sort(function(a, b) {
      return b - a;
    });
    console.log("13位数最大连乘积", mul[0]);
    

    输出为

    13位数最大连乘积: 23514624000
    [Done] exited with code=0 in 0.239 seconds

    PS: 我是个渣渣,想不出优雅的写法,唉。。。


    第九题 特殊毕达哥拉斯三元组

    毕达哥拉斯三元组是三个自然数a < b < c组成的集合,并满足a2 + b2 = c2
    例如,32 + 42 = 9 + 16 = 25 = 52
    有且只有一个毕达哥拉斯三元组满足 a + b + c = 1000。求这个三元组的乘积abc。

    var flag = false;
    for (var a = 1; a < 1000; a++) {
      for (var b = a + 1; b < 1000; b++) {
        for (var c = b + 1; c < 1000; c++) {
          if (a + b + c == 1000 && a * a + b * b == c * c) {
            console.log("a:", a, " b:", b, " c:", c);
            console.log("abc:", a * b * c);
            flag = true;
            break;
          }
        }
        if (flag) {
          break;
        }
      }
      if (flag) {
        break;
      }
    }
    

    输出为

    a: 200 b: 375 c: 425
    abc: 31875000
    [Done] exited with code=0 in 0.272 seconds


    第十题 素数的和

    所有小于10的素数的和是2 + 3 + 5 + 7 = 17。
    求所有小于两百万的素数的和。
    分析:考虑提高性能,使求解速度快。一是使用break,只要满足有解就退出小循环;二是使用Math.sqrt,只需要算一半就行

    var sum = 0;
    var num = 2000000;
    for (let i = 2; i < num; i++) {
      let flag = true;
      for (let j = 2; j <= Math.sqrt(i); j++) {
        if (i % j == 0) {
          flag = false;
          break;
        }
      }
      if (flag) {
        sum += i;
      }
    }
    console.log(sum);
    

    输出为

    142913828922
    [Done] exited with code=0 in 1.008 seconds


    持续更新中…

    展开全文
  • euler-solutions:欧拉计划中一些已解决的问题
  • 欧拉计划1-50题

    2012-03-28 18:27:42
    欧拉计划1-50题
  • 欧拉计划欧拉计划) 算法练习部分,目录分类一塌糊涂,我也不打算好好整理了,就这么乱吧解的题有欧拉计划,ZOJ(这破网站最近登不上了) 目录树 . ├── classical_clang c语言算法练习 │ ├── array 动态...
  • 欧拉计划 我通过学习其他语言的尝试
  • 欧拉计划 Java实现

    2014-02-28 20:38:13
    从今天将对欧拉计划的Java实现一天一更。 简单的分析欧拉计划的每道题。希望与大家交流学习。
  • 欧拉计划提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然还得靠编程,但编程语言不限,已经有Java、C#、Python、Lisp、Haskell等各种解法,当然直接用google搜索答案就没什么乐趣了。 这里汇总了...
  • 2019年6月18日,Facebook发布了数字货币Libra的技术白皮书,我也第一时间体验了一下它的...欧拉计划看了一下网上有关Rust的介绍,都说它的学习曲线相当陡峭,曾一度被其吓着,后来发现Rust借鉴了Haskell等函数式编程...
  • Python编程之欧拉计划35欧拉计划35、求100 万以下有多少个循环质数 欧拉计划 欧拉计划(Project Euler)。 35、求100 万以下有多少个循环质数 我们称 197 为一个循环质数,因为它的所有轮转形式: 197, 971 和 719 ...
  • Python编程之欧拉计划(16~18)欧拉计划16、求100个大数的和的前10位数字17、英文字母个数18、最大路径和 欧拉计划 欧拉计划(Project Euler)。 16、求100个大数的和的前10位数字 215=32768,32768的各位数字之和为...
  • Python编程之欧拉计划21~22欧拉计划21、求10000以内所有亲和数之和22、文件中所有名字的得分总和 欧拉计划 欧拉计划(Project Euler)。 21、求10000以内所有亲和数之和 记d(n)为n 的所有真因子(小于 n 且能整除 n ...
  • Python编程之欧拉计划26~27欧拉计划26、求出使1/d的小数表示拥有最长循环节的d值27、质数的二次公式 欧拉计划 欧拉计划(Project Euler)。 26、求出使1/d的小数表示拥有最长循环节的d值 单位分数是指分子为1的分数....
  • Python编程之欧拉计划31~32欧拉计划31、求换零钱的方法数32、找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和 欧拉计划 欧拉计划(Project Euler)。 31、求换零钱的方法数 在英国,货币是由英镑 £,...
  • Python编程之欧拉计划37~38欧拉计划37、找出所有11个可以双向裁剪的质数38、连接积和全数字 欧拉计划 欧拉计划(Project Euler)。 37、找出所有11个可以双向裁剪的质数 3797 这个数很有趣。它本身是质数,而且如果...
  • Python编程之欧拉计划(12)欧拉计划12、第一个拥有超过500个约数的三角形数 欧拉计划 欧拉计划(Project Euler)12。 12、第一个拥有超过500个约数的三角形数 三角形数数列是通过逐个加上自然数来生成的。例如,第7...
  • Python编程之欧拉计划28~30欧拉计划28、求1001×1001的螺旋中对角线上数字之和29、序列的项数30、找出所有能被写成各位数字五次方之和的数之和 欧拉计划 欧拉计划(Project Euler)。 28、求1001×1001的螺旋中对角...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,234
精华内容 493
关键字:

欧拉计划