题目74：包含60个不重复项的阶乘链有多少个？

from math import factorial as fct
def chain(n):
    chains = [n]
    count, calc = 1, 0
    for i in str(n):
        calc += fct(int(i))
    while calc not in chains:
        chains.append(calc)
        count += 1
        n1 = calc
        calc = 0
        for i in str(n1):
            calc += fct(int(i))
    return count

chainlist = []
for i in range(1,1000001):
    if i % 50000 == 0:
        middle = clock()
        print ('进度：%d' % int(i/10000), '%',' 用时：%.3f秒 >>>' % (middle-start), end ='')
    if chain(i) == 60:
        chainlist.append(i)
end = clock()
print ('答案： %d' % len(chainlist), '总共用时：%.3f秒' % (end-start))

# -*- coding: utf-8 -*-
import math
import time
start=time.clock()
list2=[]
list3=[]
list4=[]
def fen_2(m):
    list1=[]
    list2.append(m)
    for n in str(m) :
        n=int(n)
        list1.append(math.factorial(n))
    if len(list2)!=len(set(list2)):
        list2.pop()
        return len(list2)
    return  fen_2(sum(list1))
def fen(x):
    global list2
    list2 =[]
    return(fen_2(x))
for i in range(1,1000000):
    if fen(i)>=60:
        list3.append(i)
print(len(list3) )
for i in list3:
    fen(i)
    list4.extend(list(set(list2)&set(list3 )))
print(list4 == list3)
end=time.clock()
print('运行耗时:%f'%(end-start ))

# encoding:utf-8
# 寻找100万以下60项的阶乘链  145 = 1！+2！+3！
from time import time
from math import factorial

def getFac(n):
    result = 0
    while n >= 10:
        result += factorial(n % 10)
        n = n // 10
    return result + factorial(n)

def euler072(N=100):
    d_facs = {}
    s_facs = set()
    count = 0
    for n in range(1, 1000001):
        if str(sorted(str(n))) in s_facs:
            count+=1
        else:
            l_tmp = [n]
            tmp,k = 0,n
            while True:
                tmp = getFac(k);
                if tmp not in l_tmp:
                    l_tmp.append(tmp)
                    k = tmp
                else:
                    break 
            if len(l_tmp)>=60:
                count+=1
                d_facs[str(sorted(str(n)))] = l_tmp
    print(count)    
    
if __name__ == '__main__':
    start = time() 
    euler072()
    print('cost %.6f sec' % (time() - start))

from time import perf_counter


def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

def generate_unrepetition_link(n):
    unrepetition_link = [n]
    num_str = str(n)
    while True:
        sum_ = 0
        for each in num_str:
            sum_ += factorial(int(each))
        if sum_ not in unrepetition_link:
            unrepetition_link.append(sum_)
            num_str = str(sum_)
        else:
            break
    return unrepetition_link
def main():
    n = 0
    for i in range(5, 1000000):
        if len(generate_unrepetition_link(i)) == 60:
            n += 1
    print(n)


if __name__ == '__main__':
    start = perf_counter()
    main()
    end = perf_counter()
    print("time uesd:", end - start)

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

const int f[] = {1,1,2,6,24,120,720,5040,40320,362880};

const int len3[] = {169,1454,363601};
const int len2[] = {871,872,45361,45362};
const int len1[] = {0,1,2,145,40585};

const int M = 1e6;
int dp[M*10] = {0};
int mx = 0;

int f_sum(int x){
  int res = 0;
  if (x == 0) return 1;
  while(x){
    res += f[x % 10];
    x /= 10;
  }
  return res;
}

int len(int x){
  //mx = max(mx,x);
  int & ans = dp[x];
  if (ans)  return ans;

  if (find(len3,len3 +3,x) != len3 +3)  return ans = 3;
  if (find(len2,len2 +4,x) != len2 +4)  return ans = 2;
  if (find(len1,len1 +5,x) != len1 +5)  return ans = 1;

  return ans = len(f_sum(x)) + 1;
}

int main(){
  int cnt = 0;
  for (int i = 0;i <= M;i++)
    if (len(i) == 60) ++cnt;

  //cout << mx << endl;
  cout << cnt << endl;
  return 0;
}

/*
答案：402
耗时：4.07265秒（单核）
      0.658726秒（六核）
*/
#include <iostream>
#include <unordered_set>
#include <omp.h>
using namespace std;

const int f[] = { 1,1,2,6,24,120,720,5040,40320,362880 };

int GetFS(int n)
{
  int nS = 0;
  while (n > 0)
  {
    nS += f[n % 10];
    n /= 10;
  }
  return nS;
}

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
  unordered_set<long long> us;
#pragma omp parallel for private(us) reduction(+:nCount)
  for (int i = 1; i <= 1000000; ++i)
  {
    us.clear();
    int k = i;
    while (true)
    {
      auto itr = us.find(k);
      if (itr != us.end())
        break;
      us.insert(k);
      k = GetFS(k);
    }
    if (us.size() >= 60)
      ++nCount;
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}

import time
st=time.time()
n=1000000
# 获取阶乘数列
jiecheng=[1]
for i in range(1,10):
    jiecheng.append(jiecheng[-1]*i)
# 创建dict()
data=dict()
def getl(n):
    if n in data:
        return data[n]
    data2=dict()
    nn=n
    u=0
    while nn not in data2:
        num=0
        ii=nn
        while ii>0:
            num=jiecheng[ii%10]+num
            ii=ii//10
        data2[nn]=len(data2)+1
        nn=num
        if nn in data:
            u=data[nn]-1
            data2[nn]=len(data2)+1
            break
    for j in data2:
        if data2[j]>=data2[nn]:
            data[j]=len(data2)+1-data2[nn]+u
        else:
            data[j]=len(data2)+1-data2[j]+u
    return data[n]
numsum=0
for i in range(69,n+1):
    # print(getl(i))
    if getl(i)>=60:
        numsum=numsum+1
print(numsum)
# print(data)
print('Time:{}s'.format(time.time()-st))