zoj 1180 Self Numbers（大数，灵活题）

发布时间：2020-12-14 02:38:22 所属栏目：大数据来源：网络整理

导读：In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n,define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition,a term coined by Kaprekar.) Fo

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n,define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition,a term coined by Kaprekar.) For example,d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point,you can construct the infinite increasing sequence of integers n,d(n),d(d(n)),d(d(d(n))),.... For example,if you start with 33,the next number is 33 + 3 + 3 = 39,the next is 39 + 3 + 9 = 51,the next is 51 + 5 + 1 = 57,and so you generate the sequence

33,39,51,57,69,84,96,111,114,120,123,129,141,...

The number n is called a generator of d(n). In the sequence above,33 is a generator of 39,39 is a generator of 51,51 is a generator of 57,and so on. Some numbers have more than one generator: for example,101 has two generators,91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1,3,5,7,9,20,31,42,53,64,75,86,and 97.

Write a program to output all positive self-numbers less than or equal 1000000 in increasing order,one per line.

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=180

找出1000000以内所有不能由其他数字（abc+a+b+c）组成的数

因为a+b+c+...最大也就是9+9+9+9+9+9=54，所以直接暴力即可

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define ll long long
using namespace std;
int main(){
	for(int i=1;i<=1000000;++i){
		int u=0;
		for(int j=1;j<=54&&i-j>0;++j){
			int p=i-j,s=0;
			while(p>0){
				s+=p%10;
				p/=10;
			}
			if(s==j){
				u=1;
				break;
			}
		}
	  	if(u==0)
			cout<<i<<endl;
	}
	return 0;
}

不过上面的代码效率没有下面的高：

#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
int hash[1000005];
void deal(int n){
    int rec = n;
    while( n > 0 ){
        int c = n % 10;
        n /= 10;
        rec += c;
    }
    hash[rec] = 1;
}
int main(){
    for(int i=1;i<=1000000;++i){
        if(!hash[i])
            printf("%dn",i);
        deal(i);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!