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 100000
int 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 10000000000ll
long long prime[1000000];
int pl = 0;
#define ll long long
inline 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 120000
int 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 120000
int 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 long
bool 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;
}