Project Euler

概述目录 Solutions to Project Euler P125 P124 P126 P123 P122 P121 P127 P128 Solutions to Project Euler Website Written by dgklr, often by using python / c++ P125 Answer: 2906969179 Running Time: 1068ms /* C

目录

Solutions to Project Euler P125 P124 P126 P123 P122 P121 P127 P128 Solutions to Project Euler

Website

Written by dgklr,often by using python / c++

P125

Answer: 2906969179

Running Time: 1068ms

/* copyright (c) dgklr */#include<bits/stdc++.h>using namespace std;long long n;long long li[11000];long long pre[11000];bool has[110000000];const int N = 100000000;long long ans = 0;voID check(long long ret){    if (ret > N) return;    char c[11];    if (has[ret] == 1) return;    sprintf(c,"%lld",ret);    int len = strlen(c);    for (int i=0;i<len;i++){        if (c[i] != c[len-i-1]) return;    }    has[ret] = 1;    ans += ret;}int main(){    for (int i=1;i*i<=N;i++)        li[i] = i * i,pre[i] = pre[i-1] + li[i];    for (int i=2;i*i<=N;i++){        for (int j=0;j<=i-2;j++){            check(pre[i] - pre[j]);        }    }    cout << ans << endl;}

P124

Answer: 21417

Running Time: 521ms

/* copyright (c) dgklr */#include<bits/stdc++.h>using namespace std;#define N 100000int pl = 0;int prime[N];int trans(int x){    int ret = 1;    for (int i=1;i<=pl;i++){        if (x % prime[i] == 0)  ret *= prime[i];        while (x % prime[i] == 0) x /= prime[i];        if (x == 1) break;    }    return ret;}int getprime(){    for (int i=2;i<=N;i++){        int flag = 0;        for (int j=2;j*j<=i;j++)            if (i % j == 0) {flag = 1; break;}        if (!flag) prime[++pl] = i;    }}pair <int,int> ans[N+2];int main(){    getprime();    for (int i=1;i<=N;i++){        ans[i].first = trans(i);        ans[i].second = i;    }    sort(ans+1,ans+N+1);    cout << ans[10000].second;}

P126

Answer: 18522

Running Time: 81ms

/* copyright (c) dgklr */#include<bits/stdc++.h>#define DEBUG cerr << "Call out: " << __func__ << "\t" << "line: " << __liNE__ << "\t :"using namespace std;const int N = 30000;int C[N + 4];int Cubes(int x,int y,int z,int n) {    return 2 * (x * y + y * z + x * z ) + 4 * (x + y + z + n - 2) * (n - 1);}int main(){    clock_t beg = clock();    for (int i=1;Cubes(i,i,1) <= N;i++)        for (int j=i;Cubes(i,j,1) <= N;j++)            for (int k=j;Cubes(i,k,1) <= N;k++)                for (int l=1;Cubes(i,l) <= N;L++)                    C[Cubes(i,l)] ++;    for (int i=1;i<=N;i++)        if (C[i] == 1000) cout << i << ' ' << clock()-beg << endl,exit(0);}

P123

Answer: 21035

Running Time: 740ms

/* copyright (c) dgklr */#include<bits/stdc++.h>#define DEBUG cerr << "Call out: " << __func__ << "\t" << "line: " << __liNE__ << "\t :"using namespace std;#define MAXN 10000000000lllong long prime[1000000];int pl = 0;#define ll long longinline ll ksc(ll x,ll y,ll p){    ll res=0;    while(y){        if(y&1)res=(res+x)%p;        x=(x<<1)%p; y>>=1;    }return res;}long long ksm(long long x,long long base,long long MOD){    long long ret = 1;    long long xt = x;    while (base > 0){        if (base % 2 == 1) ret = ksc(ret,xt,MOD);        xt = ksc(xt,MOD);        base /= 2;    }    return ret;}voID getprime(){    for (int i=2;i<=1000000;i++){        int flag = 0;        for (int j=2;j*j<=i;j++){            if (i%j == 0) {flag = 1; break;}        }        if (!flag) prime[++pl] = i;    }}int main(){    clock_t beg = clock();    getprime();    for (int i=1;i;i++){        if ((ksm(prime[i]-1,prime[i]*prime[i]) + ksm(prime[i]+1,prime[i]*prime[i]))%(prime[i]*prime[i]) > MAXN)            cout << i << ' ' << clock() - beg << "ms"<< endl,exit(0);    }}

P122

Answer: 1582

Running Time:1544ms

/* copyright (c) dgklr */#include<bits/stdc++.h>using namespace std;const int MAXK = 200;int opt[20] = {0,1};int ansList[210] = {0,1};voID dfs(int Now,int x){    if (x > 12) return;    if (Now > MAXK) return;    if (ansList[Now] > x) ansList[Now] = x;    opt[x] = Now;    for (int i=1;i<=x;i++){        dfs(Now+opt[i],x+1);    }}int main(){    int beg = clock();    int ans = 0;    memset(ansList,0x3f,sizeof ansList);    ansList[1] = 1;    dfs(2,2);    for (int i=1;i<=MAXK;i++){        ans += ansList[i]-1;    }    cout << ans << ' ' <<clock() - beg << "ms" << endl;}

P121

ans: 2269

Running Time: 0ms

/* copyright (c) dgklr */#include<bits/stdc++.h>using namespace std;double f(int n,int i,int r,int b){    if (i == n) return b > r ? 1 : 0;    return 1 * f(n,i + 1,r,b + 1) / (i + 2) + (i + 1) * f(n,r + 1,b) / (i + 2);}int main(){    int beg = clock();    cout << (int)(1 / f(15,0)) << endl;    cout << clock() - beg << "ms" << endl;    return 0;}

P127

Answer: 18407904

A Better Solution

Running Time: 257ms

#include<bits/stdc++.h>#define DEBUG cerr << "Call out: " << __func__ << "\t" << "line: " << __liNE__ << "\t :"using namespace std;#define MAXN 120000int rad[120000];int prime[120000];int tot[120000];int pl;voID getprime(){    for (int i=2;i<=MAXN;i++){        int flag = 0;        for (int j=2;j*j<=i;j++){            if (i%j == 0) {flag = 1; break;}        }        if (!flag) prime[++pl] = i;    }}int init(){    for (int i=1;i<=MAXN;i++){        int tmp = i;        rad[i] = 1;        for (int j=1;j<=pl;j++){            if (tmp % prime[j] == 0) {                rad[i] *= prime[j];                while (tmp % prime[j] == 0) tmp /= prime[j];            }            if (tmp == 1) break;            if (prime[j] * prime[j] > tmp){                rad[i] *= tmp;                break;            }        }    }    for (int i=1;i<=MAXN;i++){        tot[rad[i]] ++;    }}long long ans = 0;set <pair<int,int> > p;int process(int x,int has){    int ret = 0;    for (auto i : p){        if (i.first * i.first > x) return ret;        if (__gcd(i.second,x) == 1 && __gcd(i.second,has-i.second) == 1 && i.first < rad[has-i.second]){            if (i.first * rad[has-i.second] < x) ret += has;        }    }    return ret;}int main(){    clock_t beg = clock();    getprime();    init();    p.insert(make_pair(1,1));    for (int i=2;i<MAXN;i++){        ans += process(i/rad[i],i);        p.insert(make_pair(rad[i],i));    }    cout << ans << ' ';    cout << clock() - beg << endl;}

Running time: 1111ms

#include<bits/stdc++.h>#define DEBUG cerr << "Call out: " << __func__ << "\t" << "line: " << __liNE__ << "\t :"using namespace std;#define MAXN 120000int rad[120000];int prime[120000];int tot[120000];int pl;voID getprime(){    for (int i=2;i<=MAXN;i++){        int flag = 0;        for (int j=2;j*j<=i;j++){            if (i%j == 0) {flag = 1; break;}        }        if (!flag) prime[++pl] = i;    }}int init(){    for (int i=1;i<=MAXN;i++){        int tmp = i;        rad[i] = 1;        for (int j=1;j<=pl;j++){            if (tmp % prime[j] == 0) {                rad[i] *= prime[j];                while (tmp % prime[j] == 0) tmp /= prime[j];            }            if (tmp == 1) break;            if (prime[j] * prime[j] > tmp){                rad[i] *= tmp;                break;            }        }    }    for (int i=1;i<=MAXN;i++){        tot[rad[i]] ++;    }}long long ans = 0;set <pair<int,int has){    map <int,int> h;    int ret = 0;    for (auto i : p){        h[i.second] = 1;        if (i.first * i.first > x) return ret;        if (__gcd(i.second,has-i.second) == 1 && h[has-i.second] == 0){            if (i.first * rad[has-i.second] < x) ret += has;        }    }    return ret;}int main(){    clock_t beg = clock();    getprime();    init();    p.insert(make_pair(1,i));    }    cout << ans << ' ';    cout << clock() - beg << endl;}

P128

Answer: 14516824220

Running Time: 201ms

/* copyright (c) dgklr */#include<bits/stdc++.h>using namespace std;#define int long longbool IsPrime(int x){    for (int i=2;i * i <=x;i++){        if (x % i == 0) return 0;    }    return 1;}signed main(){    int beg = clock();    int count = 1;    int limit = 2000;    int n = 0;    int number = 0;    while (count < limit)    {        n++;        if (IsPrime(6 * n - 1) && IsPrime(6 * n + 1) && IsPrime(12 * n + 5))        {            count++;            number = (3 * n * n - 3*n + 2);            if (count >= limit) break;        }        if (IsPrime(6 * n + 5) && IsPrime(6 * n - 1) && IsPrime(12 * n - 7) && n != 1)        {            count++;            number = (3 * n * n + 3*n + 1);        }    }    cout << number << ' ' << clock() - beg << "ms" << endl;    return 0;}

总结

以上是内存溢出为你收集整理的Project Euler全部内容，希望文章能够帮你解决Project Euler所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。