题目92：考察具有有趣性质的平方数链

#include <iostream>
#include <vector>
#include <algorithm>
using namespace  std;
/*
返回一个数字各位数平方相加后的数
*/
int get(int num)
{
        int sum=0;
        int t = num;
        while(num)
        {
                sum+= (num%10)*(num%10);
                num/=10;
        }
        return sum;
}
int main()
{
        //限制从1KW
        vector<int> result;
        int j = 0;
        int sum=0;//统计有89的数字
        for (int i =1;i<=10000000;i++)
        {
                j=i;
                int value = 0;
                
        
                        //获取这个数字各位数平方和
                        while(1)
                        {

                        
                                value = get(j);
                                if(value==89) sum++;
                                if(result.end()==find(result.begin(),result.end(),value))
                                {
                                        //没找到到了 
                                        result.push_back(value);
                                        j=value;
                                        
                                }else
                                {
                                        //找到 退出
                                        result.push_back(value);
                                        break;
                                           
                                }

                        }
                        //输出结果
                        
                        //std::cout<<i<<":";
                        for (int m=0;m<result.size();m++)
                        {
                                //std::cout<<result[m]<<" ";
                        }
                        //std::cout<<endl;
                        result.clear();
        
        }
        std::cout<<"结果"<<sum<<endl;
        return 0;
}

def get_sum(x):
    number_list = []
    while x:
        x,temp = divmod(x,10)
        number_list.insert(0,temp)
    return sum([t*t for t in number_list])

num_dict = {}

for i in range(1,600):
    s = i
    while s != 1 and s != 89:
        if num_dict.get(s,0):
            s = num_dict[s]
            break
        s = get_sum(s)
    num_dict[i] = s

count_89 = 0
for i in range(1,10000001):
    s = get_sum(i)
    if num_dict[s] == 89:
        count_89+=1
        
print(count_89)

def chain(n):
        i = n
        while True:
                s = 0
                while True:
                        s += (i%10)**2
                        i = int(i/10)
                        if i == 0:
                                break
                i = s
                if i == 89:
                        return True
                elif i == 1:
                        return False
                else:
                        pass

count = 0
for i in range(2,10000000):
        if chain(i):
                count += 1
print count

def Loop(x,count=0):
    while x!=1 and x!=89:
        for each in str(x):
            count += int(each)**2
        x = count
        count = 0
    if x ==89:
        return True
    if x == 1:
        return False
total = 0
for i in range(1,10000000):
    if Loop(i,count=0):
        total += 1
print(total)

# encoding:utf-8
# 具有有趣性质的平方数链
from time import time
N = 10000000
flag = [0] * (N + 1)
def getNums(n):
    while (n != 1 and n != 89):
        if flag[n] == 1:
            return 1
        elif flag[n] == 89:
            return 89
        sums = 0
        for x in str(n):
            sums += (int(x)) ** 2
        n = sums
    return n

def euler092(N):
    for n in range(1, N):
        t = getNums(n)
        # print(n,t)
        if t == 1:
            flag[n] = 1
        else:
            flag[n] = 89
    print(len([k for (k, v) in enumerate(flag) if v == 89]))       

if __name__ == '__main__':
    start = time() 
    euler092(N)
    print('cost %.6f sec' % (time() - start))

#include<iostream>



constexpr unsigned char arrive_at(unsigned int x)noexcept {
    constexpr unsigned char squares[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
    static unsigned char cache[7 * squares[9] + 1] = {[1] = 1, [89] = 89};
    unsigned int temp; 
    unsigned short res = 0;

    while (x) {
        temp = x;
        x /= 10;
        res += squares[temp - x * 10];
    }

    if (cache[res]) {
        return cache[res];
    }

    return cache[res] = arrive_at(res);
}



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    unsigned int count = 0, num;


    for (num = 1; num < 10000000; num++) {
        count += arrive_at(num) == 89;
    }


    cout << count << endl;
    return 0;
}

def get_sum(x):
    result = 0
    
    while x:
        x,temp = divmod(x,10)
        result += temp * temp
    
    return result

#include<iostream>
using namespace std;

const int M = 1e7;
int e[M] = {0};

int square_sum(int x){
  int res = 0;
  int x0 = x;
  if (e[x0])  return e[x0];

  while(x){
    int t = x % 10;
    res += t*t;
    x /= 10;
  }

  if (res == 1 || res == 89) return e[x0] = res;
  return e[x0] = square_sum(res);
}

int main(){
  int cnt = 0;

  for (int i = 1;i < M;i++){
    square_sum(i);
    if (e[i] == 89) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

/*
答案：8581146
耗时：0.314319秒（八核）
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;

int v1[5] = { 1,10,13,32,44 };
int v89[9] = { 4,16,20,37,42,58,85,89,145 };
int S[10] = { 0,1,4,9,16,25,36,49,64,81 };

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
#pragma omp parallel for shared(v1,v89,S) reduction(+:nCount)
  for (int n = 1; n <= 10000000; ++n)
  {
    int k = n;
    bool bFind = false;
    while (true)
    {
      int nSum = 0;
      while (k != 0)
      {
        nSum += S[k % 10];
        k /= 10;
      }
      if (binary_search(v1, v1 + 5, nSum))
        break;
      if (binary_search(v89, v89 + 9, nSum))
      {
        bFind = true;
        break;
      }
      k = nSum;
    }
    if (bFind)
      ++nCount;
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}