首页 > ACM题库 > HDU-杭电 > HDU 1333 Smith Numbers-数论-[解题报告] C++
2013
12-09

HDU 1333 Smith Numbers-数论-[解题报告] C++

Smith Numbers

问题描述 :

While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University, noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith’s telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:

4937775 = 3 * 5 * 5 * 65837

The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42?, and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7= 42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.

As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.

Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!

输入:

The input consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.

输出:

For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n, and print it on a line by itself. You can assume that such a number exists.

样例输入:

4937774
0

样例输出:

4937775 

所有的,今天是没怎么玩就开始敲代码了..我是喜欢敲代码,也是喜欢解决自己的问题,

也是喜欢自己一天一天的进步,但是,我没有那么多的时间陪别人去耗,所以呢,,我现在就得养成那么一个习惯,,

学什么知识点就学一遍,然后无数遍的温习,永远的记住.

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

using namespace std;

int getsum (int x) // getsum_all_letter的函数,我觉得是一个不错的函数, 
{
	int sum = 0;
	while (x)
	{
		sum += x % 10;
		x /= 10;
	}
	return sum;
}


int main ()
{
	int N;
	while (cin >> N)
	{
		if (N == 0)
		{
			break;
			
		}
		for (int x = N + 1; ; x++)
		{
			int key = x;  // 因为你最后还要把这个数字输出来,所以要提前把初始的数字先存起来. 
			int sum_all_letter = getsum (key); //所求的和; 
			int sum_prime = 0; //分解质因数的和; 
			int flag_prime = 0;//标记是x是不是一个素数; 
			for (int i = 2; i <= sqrt (key * 1.0); i++)
			{
				while (key % i == 0)
				{
					flag_prime++;  //这个就是标记:看初始状态的key是不是个素数,如果是素数就得祛除. 
					sum_prime += getsum (i); //方法很奇特. 
					key /= i;
				}
			}
			if (key != 1)
			{
				sum_prime += getsum (key); // 就是排除除到了最后出现了一个prime number,所以加个语句,判断最后的 
			}								//那个除数是不是素数. 
			if (sum_all_letter == sum_prime && flag_prime != 0) //这个思想是真的很不错的, 
			{
				cout << x << endl;
				break;
			}
		}
	}
	return 0;
}
/*
这道题目真的是个好题目,因为涉及的知识点很多, 有怎么样求一个整数的所有数字的和的算法getsum,
也有最正确的求整数的素因数分解的算法...诶.
这个晚上就是搞这个题目了,真的很恨自己呀,,老是出错,一次一次的敲也不往自己的心里面去.
那这样的学习,你就还不如回宿舍里面好好的休息呢..或者去陪你的女朋友去,我一直都认为,
你一直都这样的告诉你自己,如果自己没有真心的学会,那就别做,,你做也不是白做么??仅仅是浪费自己的时间,
浪费自己的青春.
*/

解题报告转自:http://blog.csdn.net/qinaide_lixiaoshuo/article/details/8201414


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  4. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }