プロジェクトオイラー問159 - sinapusu2002 @ ウィキ

https://projecteuler.net/problem=159

探索範囲が狭いので深さ優先多作による全探索とちょっとしたメモ化で答えが出ます。

#include<stdio.h>
#include<algorithm>
#include<iostream> 

const int LIMIT=1000*1000;
int memo[LIMIT]={0};
int ans[LIMIT]={0};
 
void kon(int n){
	int m=n;
	while(1){
		if(m<10)break;
		int sum=0;
		while(m>0){
 			sum+=m%10;
			m/=10;
		}
 		m=sum;
 	}
	memo[n]=m;
}

void f(__int64 a,int d,int sum){
	ans[(int)a]=std::max(ans[(int)a],sum);
 	for(__int64 i=d;i<LIMIT;i++){
		if(a*i>=LIMIT)break;
 		f(a*i,i,sum+memo[(int)i]);
	}
}
int main(){
 	for(int i=1;i<LIMIT;i++)kon(i);
	f(1,2,0);
	__int64 ansA=0;
	for(int i=1;i<LIMIT;i++)ansA+=ans[i];
	std::cout<<"ans="<<ansA<<"\n";
}