Project Euler

Sep 20, 2015


## 30. Digit fifth powers ##

我们可以计算出枚举的上限。6位数的时候,$6*9^5 = 354294 \leq 999999$,那么极限就是354294。

ans = 0
for i in range(2, 400000):
    s = str(i)
    add = 0
    for j in s:
        add += (ord(j)-ord('0'))**5
    if add == i:
        ans += add
print ans

## 29. Distinct powers ##

枚举。

vis = set()
for i in range(2, 101):
    for j in range(2, 101):
        vis.add(i**j)
print len(vis)

## 27. Number spiral diagonals ##

枚举。

import math
 
def cal(n, a, b):
    return n*n + a*n + b
 
def is_prime(n):
    if n <= 1:
        return False
    m = int(math.sqrt(n+0.5))
    for i in range(2, m+1):
        if n % i == 0:
            return False
    return True
 
prime = set()
max_cnt = 0
 
for a in xrange(-999, 1000):
    for b in xrange(-999, 1000):
        n = 0
        while True:
            if cal(n, a, b) in prime:
                n += 1
            elif is_prime(cal(n, a, b)):
                prime.add(cal(n, a, b))
                n += 1
            else:
                if n > max_cnt:
                    max_cnt = n
                    ans = a*b
                break
print ans

## 26. Reciprocal cycles ##

我们知道,x可以被9、99、999等的第一个数整除,1/x的循环节的位数就是9的个数。 那么我们枚举一下即可。

ans = 0
cur_ans = 0
for i in range(1, 1000):
    num = 9
    while i % 2 == 0:
        i /= 2
    while i % 5 == 0:
        i /= 5
    if i == 1:
        continue
    while True:
        if num % i == 0:
            break;
        num = num * 10 + 9
    if len(str(num)) > cur_ans:
        cur_ans = len(str(num))
        ans = i
print ans

## 25. Reciprocal cycles ##

暴力。

f = [1, 1]
while True:
    f.append(f[-1]+f[len(f)-2])
    if len(str(f[-1])) == 1000:
        print len(f)
        break

## 24. Lexicographic permutations ##

偷懒。如果要更快的话可以用数学规律算出来。

import itertools
 
li = '0123456789'
it = itertools.permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
mp = list(it)
print mp[1000000-1]

## 23. Non-abundant sums ##

暴力枚举。

import math
nums = []
 
def get_abundant_numbers():
    for i in range(2, 28124):
        m = int(math.sqrt(i))
        cur = 0
        for j in range(2, m+1):
            if i % j == 0:
                cur += j
                if j*j != i:
                    cur += i/j
        if cur > i:
            nums.append(i)
 
def solve():
    vis = set()
    ans = 0
    for i in nums:
        for j in nums:
            vis.add(i+j)
    for i in range(1, 28124):
        if i not in vis:
            ans += i
    print ans
 
get_abundant_numbers()
solve()

## 21. Amicable numbers ##

暴力枚举约数。

import math
 
mp = {}
aans = 0
def handle(n):
    if mp.has_key(n):
        return mp[n]
    m = int(math.sqrt(n))
    global aans
    ans = 0
    for i in range(2, m+1):
        if n % i == 0:
            ans += i
            if i*i != n:
                ans += n / i
    ans += 1
    mp[n] = ans
for i in range(2, 10000):
    handle(i)
for i in range(2, 10000):
    if mp[i] != i and mp[i] < 10000 and mp[i] != 1 and mp[mp[i]] == i:
        aans += i
print aans

## 20. Factorial digit sum ##

暴力。

import math
 
ans = 0
for i in str(math.factorial(100)):
    ans += int(i)
print ans

## 19. Counting Sundays ##

枚举。

num = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
 
cur = 5
ans = 0
 
def check(n):
    if n % 100 == 0:
        if n % 400 == 0:
            return True
        else:
            return False
    else:
        return n % 4 == 0
 
for i in range(1901, 2001):
    for j in range(12):
        for k in range(num[j]):
            cur = (cur+1) % 7
            if k == 0 and cur == 6:
                ans += 1
        if check(i) and j == 1:
            cur = (cur+1) % 7
print ans

## 18. Maximum path sum I ##

简单dp。

dp = {}
 
def dfs(x, y):
    if (x >= len(mp) or y >= len(mp[x])):
        return 0
    if dp.has_key((x, y)):
        return dp[(x, y)]
    dp[(x, y)] = max(dfs(x+1, y), dfs(x+1, y+1)) + mp[x][y]
    return dp[(x, y)]
 
f = file('Y:\input.txt', 'r')
 
mp = []
for i in f.readlines():
    mp.append([])
    for j in i.split():
        mp[len(mp)-1].append(int(j))
print dfs(0, 0)

## 17. Number letter counts ##

先写出全部的单词。统计一下前100的,然后100以上的直接x100 + 前100字母数。 统计前100的时候先统计出前10的,后面直接x10 + 前10.

word = [['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'], ['ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen'], ['twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']]
 
nine_words = 0
for i in word[0]:
    nine_words += len(i)
ans = 0
for i in word[1]:
    ans += len(i)
ans += nine_words
for i in word[2]:
    ans += len(i)*10 + nine_words
ninety_nine = ans
for i in word[0]:
    ans += 100*(len(i)+10) + ninety_nine
    ans -= 3
ans += 11
print ans

## 16. Power digit sum ##

暴力。

ans = 0
for i in str(2**1000):
    ans += int(i)
print ans

## 15. Lattice paths ##

基础dp。

dp = [[]]
for i in range(30):
    dp.append([])
    for j in range(30):
        dp[i].append(0)
dp[1][1] = 1
for i in range(1, 22):
    for j in range(1, 22):
        dp[i][j] += dp[i][j-1] + dp[i-1][j]
        #print dp[i][j]
print dp[21][21]

## 14. Longest Collatz sequence ##

要记忆化搜索。

mp = {}
mp[1] = 0
 
def Solve(n):
    tmp = n
    cnt = 0
    while True:
        if mp.has_key(n):
            mp[tmp] = cnt + mp[n]
            return mp[tmp]
        if n & 1:
            n = 3*n+1
        else:
            n = n / 2
        cnt += 1
 
ans = 0
pos = 0
for i in range(1000001, 0, -1):
    tmp = Solve(i)
    if tmp > ans:
        ans = tmp
        pos = i
print pos

## 13.Large sum ##

直接搞。

f = file('Y:\input.txt', 'r')
mp = []
for i in f.readlines():
    mp.append(int(i.strip()))
print str(sum(mp))[:10]

## 12. Highly divisible triangular number ##

根据唯一分解定理,约数是(各个质因数数目+1)相乘。

import math
 
def Calc(n):
    ret = 1
    m = int(math.sqrt(n))
    for i in range(2, m+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n /= i
        ret *= (cnt+1)
    if (n != 1):
        ret *= 2
    return ret

 
cur = 0
cnt = 1
 
while True:
    cur += cnt
    cnt += 1
    ans = Calc(cur)
    if (ans >= 500):
        print cur
        break

## 11. Largest product in a grid ##

枚举。

def Solve():
    dirc = ((0, 1), (1, 0), (1, 1), (1, -1))
    ans = 1
    for i in range(len(mp)):
        for j in range(len(mp)):
            for k in range(len(dirc)):
                tmp = 1
                l = 0
                for l in range(4):
                    x = i + l*dirc[k][0]
                    y = j + l*dirc[k][1]
                    if (x >= len(mp) or y >= len(mp) or x < 0 or y < 0):
                        break;
                    tmp *= int(mp[x][y])
                #print 'row %d col %d ans = %d' % (i, j, tmp)
                ans = max(ans, tmp)
    return ans
 
mp = []
f = file('Y:\input.txt', 'r')
for i in f.readlines():
    mp.append(i.strip().split())
print Solve()

## 10. Summation of primes ##

筛。

import math
 
vis = set()
MAXN = int(2e6)
 
def get_prime():
    ans = 0
    m = int(math.sqrt(MAXN+0.5))
    for i in range(2, m+1):
        if i not in vis:
            for j in range(i*i, MAXN, i):
                vis.add(j)
    for i in range(2, MAXN):
        if i not in vis:
            ans += i
    return ans

print get_prime()

## 9. Special Pythagorean triplet ##

枚举。

for i in range(1001):
    for j in range(i+1, 1001):
        k = 1000 - i - j
        if (i**2 + j**2 == k**2):
            print i*j*k

## 8. Largest product in a series ##

枚举。我一直一直以为这是一个矩阵!!!

f = open('Y:\\input.txt', 'r')
string = ''
for line in f.readlines():
    line = line.strip()
    string += line
ans = 0
for i in range(len(string)-12):
    mul = 1
    for j in range(i, i+13):
        mul = mul * int(string[j])
    ans = max(ans, mul)
print ans

## 7. Sum square difference ##

## 6. 10001st prime ##

素数筛。

## 5. Smallest multiple ##

输出1~20的最小公倍数

int main()
{
    int res = 1;
    for (int i = 2; i <= 20; i++)
        res = res / __gcd(res, i) * i;
    cout << res << endl;
    return 0;
}

## 4. Largest palindrome product ##

输出三位数相乘最大的回文数

bool Check(int num)
{
    char str[10];
    MS(str, 0);
    sprintf(str, "%d", num);
    string s = str, comp = s;
    reverse(s.begin(), s.end());
    if (s == comp) return true;
    return false;
}
  
int main()
{
    int ans = 0;
    for (int i = 100; i < 1000; i++)
        for (int j = 100; j < 1000; j++)
            if (Check(i * j)) ans = max(ans, i * j);
    cout << ans << endl;
}

## 3. Largest prime factor ##

输出给定的数的最大素数项

int main()
{
    LL num = 600851475143ll;
    set<int> st;
    for (LL i = 2; i <= (LL)sqrt(600851475143ll); i++)
    {
        while (num % i == 0)
        {
            st.insert(i);
            num /= i;
        }
    }
    cout << *st.rbegin() << endl;
    return 0;
}

## 2. Even Fibonacci numbers ##

输出400W以内的Fibonacci数列中的偶数项的和

int main()
{
    const int MAX = 4e6;
    ULL ans = 0;
    int fir = 1, sec = 2, tmp = 3;
    while (1)
    {
        if (tmp > MAX) break;
        if (!(tmp&1)) ans += tmp;
        fir = sec + tmp;
        swap(fir, tmp);
        swap(fir, sec);
    }
    cout << ans + 2 << endl;
}

## 1. Multiples of 3 and 5 ##

字面意思

int main()
{
    int ans = 0;
    for (int i = 1; i < 1000; i++)
        if (i % 5 == 0 || i % 3 == 0) ans += i;
    printf("%d\n", ans);
}