昨晚突然想起,将整数分解到十进制的每一位也是很耗时的,于是改代码如下,可以将最差情况下耗时0.140秒所见到0.062秒
程序代码:
#include <vector>
// 返回 1-1,1-2,1-3,……,1-N 之内有多少个快乐数
std::vector<unsigned> foo( unsigned N )
{
unsigned s1[7] = { 0, 0, 0, 0, 0, 0, 0 };
unsigned s2[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
std::vector<char> a( 5000001, 0 ); // 0表示未决,1表示正在判断,2表示非快乐数,3表示快乐数
a[1] = 3; // 1是快乐数
for( unsigned n=1; n<=N; ++n )
{
// 加快将整数分解到一位位
for( size_t i=0; ; ++i )
{
if( s1[i] == 9 )
{
s1[i] = 0;
s2[i] = s2[i+1];
}
else
{
++s1[i];
s2[i] = s2[i+1] + s1[i]*s1[i];
for( size_t j=i; j!=0; --j )
s2[j-1] = s2[i];
break;
}
}
unsigned sigma = s2[0];
// 跳过已判断的数
if( a[n] != 0 )
continue;
// 对于大部分的数,一次求和就能得到答案,因此加此快速通道
//unsigned sigma = 0;
//for( unsigned t=n; t!=0; t/=10 )
// sigma += (t%10)*(t%10);
if( a[sigma] != 0 )
{
a[n] = a[sigma];
continue;
}
std::vector<unsigned> tmp( 1, n ); // 用以保存正在判断的数(a[sigma]==1),目的是为了加快速度
for( unsigned m=sigma; ; )
{
a[m] = 1;
tmp.push_back( m );
// 平方和
unsigned sigma = 0;
for( unsigned t=m; t!=0; t/=10 )
sigma += (t%10)*(t%10);
// 在a中查找sigma
if( a[sigma] == 0 )
{
m = sigma;
}
else
{
// 当生成的数已经出现(a[sigma]==1)或当生成的数为非快乐数(a[sigma]==2)时,将所有正在判断的数(a[sigma]==1)置为非快乐数(2)
// 当生成的数为快乐数(a[sigma]==3)时,将所有正在判断的数(a[sigma]==1)置为非快乐数(3)
char v = a[sigma]!=3 ? 2 : 3;
for( std::vector<unsigned>::const_iterator itor=tmp.begin(); itor!=tmp.end(); ++itor )
a[*itor] = v;
break;
}
}
}
// 返回
std::vector<unsigned> ret( N+1, 0 );
for( unsigned i=1; i<=N; ++i )
ret[i] = ret[i-1] + (a[i]-2);
return ret;
}
#include <iostream>
using namespace std;
int main()
{
unsigned T;
cin >> T;
std::vector<unsigned> Ns( T, 0 );
unsigned max_N = 0;
for( unsigned i=0; i<T; ++i )
{
cin >> Ns[i];
if( max_N < Ns[i] )
max_N = Ns[i];
}
std::vector<unsigned> result = foo( max_N );
for( unsigned i=0; i<T; ++i )
{
cout << result[ Ns[i] ] << '\n';
}
return 0;
}