ProjectEuler Solution Part 2 (P11 - P20)

Project Euler #12: Highly divisible triangular number

这题直接去暴力做会TLE，但是由于$N$比较小，所以我们可以打表！下面C++代码是打表程序，Python代码是提交代码。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

long long tri(int n) {
    return (long long)n * (n + 1) / 2;
}

int get_num_fac(long long num) {
    int res = 0;
    for (int i = 1; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            if (i * i == num)
                res += 1;
            else
                res += 2;
        }
    }
    return res;
}
            

int main() {
    int best = 1;
    for (int i = 1; best <= 1000; i++) {
        if (get_num_fac(tri(i)) > best) {
            printf("(%lld, %d),\n", tri(i), get_num_fac(tri(i)));
            best = get_num_fac(tri(i));
        }
    }
        
    return 0;

}

ans = [
    (3, 2),
    (6, 4),
    (28, 6),
    (36, 9),
    (120, 16),
    (300, 18),
    (528, 20),
    (630, 24),
    (2016, 36),
    (3240, 40),
    (5460, 48),
    (25200, 90),
    (73920, 112),
    (157080, 128),
    (437580, 144),
    (749700, 162),
    (1385280, 168),
    (1493856, 192),
    (2031120, 240),
    (2162160, 320),
    (17907120, 480),
    (76576500, 576),
    (103672800, 648),
    (236215980, 768),
    (842161320, 1024)
]


test = int(raw_input())

for cas in range(test):
    n = int(raw_input())
    for a, b in ans:
        if b > n:
            print a
            break

Project Euler #13: Large sum

N = int(raw_input())

ans = 0
for i in range(N):
    num = int(raw_input())
    ans += num
print str(ans)[0:10]

Project Euler #14: Longest Collatz sequence

直接暴力做会TLE，所以这里我们需要记忆化，保存以下中间结果。但是Python会爆出Memory Error的错误，所以这里给出C++解法。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 5000010;
int tmp_ans[maxn], ans[maxn], sum_ans[maxn];

int get_len(long long n) {
    int res = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = n * 3 + 1;
        }
        res += 1;
        if (n < maxn && tmp_ans[n] != 0) {
            res += tmp_ans[n];
            break;
        }
    }
    return res;
}


void init() {
    for (int i = 1; i < 5000000; i++) {
        if (tmp_ans[i] == 0)
            tmp_ans[i] = get_len((long long)i);
        if (tmp_ans[i] >= sum_ans[i-1]) {
            sum_ans[i] = tmp_ans[i];
            ans[i] = i;
        } else {
            sum_ans[i] = sum_ans[i-1];
            ans[i] = ans[i-1];
        }
    }
}

int main() {
    init();
    int test, n;
    scanf("%d", &test);
    for (int cas = 1; cas <= test; cas++) {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

Project Euler #15: Lattice paths

• 这里使用Python的二维数字，要注意浅拷贝问题，详见：http://www.cnblogs.com/btchenguang/archive/2012/01/30/2332479.html
• 这里要预处理组合数。

c = [([0] * 1001) for i in range(1001)]
mod = 1000000007

for i in range(1001):
    c[i][0] = 1
    c[i][i] = 1
for i in range(1, 1001):
    for j in range(1, i):
        c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod

test = int(raw_input())

for cas in range(test):
    n, m = map(int, raw_input().split())
    print c[n + m][n] % mod

Project Euler #16: Power digit sum

test = int(raw_input())

for cas in range(test):
    n = int(raw_input())
    print sum(map(int, str(2 ** n)))

Project Euler #17: Number to Words