[UVa] 10042 - Smith Numbers

題目網址: http://goo.gl/pZxqJH

題意: 一數若滿足其每個位數和等於其每個因數的位數和，且此數不是質數，那此數就叫 Smith Number。



解法:  直接暴力做。

TAG: Math

注意:

程式碼:

	/**
	* Tittle: 10042 - Smith Numbers
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/08
	* File: 10042 - Smith Numbers.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define EPS 1e-8
	#define N 100005
	// declarations
	int t;
	int n;
	bool isprime[N];
	int pcnt;
	int prime[10000];
	// functions
	int sumDig( int v )
	{
	static int ret;
	ret = 0;
	while( v ) {
	ret += v%10;
	v /= 10;
	}
	return ret;
	}
	// main function
	int main( void )
	{
	// input & init
	int sum1, sum2;
	int tmp;
	scanf( "%d", &t );
	pcnt = 0;
	clr( isprime, true );
	isprime[0] = isprime[1] = false;
	for( int i=2; i<=10000; ++i ) if( isprime[i] ) {
	prime[++pcnt] = i;
	for( int j=i*i; j<=10000; j+=i )
	isprime[j] = false;
	}
	while( t-- ) {
	scanf( "%d", &n );
	// solve
	for( int u=n+1; ; ++u ) {
	if( u<=10000 && isprime[u] ) continue;
	sum1 = sum2 = 0;
	sum1 = sumDig( u );
	tmp = u;
	for( int i=1; i<=pcnt && prime[i]<=tmp; ++i ) {
	while( tmp%prime[i] == 0 ) {
	tmp /= prime[i];
	sum2 += sumDig( prime[i] );
	}
	}
	if( tmp == u ) continue;
	if( tmp != 1 ) sum2 += sumDig( tmp );
	if( sum1 == sum2 ) {
	printf( "%d\n", u );
	break;
	}
	}
	}
	return 0;
	}

view raw 10042 - Smith Numbers.cpp hosted with ❤ by GitHub