糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1142 Smith Numbers 数字游戏

题目大意：
有个叫smith的人，闲得蛋疼，做了如下定义：
如果一个数分解的质因数的所有位数的和加在一起等于该数字的所有位数的和，则这个数是“smith数”。
比如：
4937775= 3*5*5*65837
 4+9+3+7+7+7+5= 42
3+5+5+6+5+8+3+7=42
则4937775是“smith数”。
另外：素数不是“smith数”
给出一个数字，求出比该数字大的数中最小的“smith数”。


思路：
按照常规方法，从2一直向上扫描，遇到能除的就除，求出数字的质因数。
但要注意，如果扫到大于该数字的平方，就没必要继续扫了，一定是素数。没加这个就是TLE。
另外，如果现有的和已经超过了最大的可能和，也没必要继续扫了。

#include <stdio.h>
#include <math.h>

__inline int digit_sum(int val)
{
    int i;

    for (i = 0; val; val /= 10)
        i += val % 10;
    return i;
}

__inline int is_smith(int val)
{
    int i, fs, max_sum, left, sum, sq;

    max_sum = digit_sum(val);
    sum = 0;
    left = val;
    sq = (int)sqrt((float)left);
    for (i = 2; i <= sq; i++) {
        if (left % i)
            continue;
        fs = digit_sum(i);
        while (!(left % i)) {
            sum += fs;
            left /= i;
        }
        if (left == 1)
            return sum == max_sum;
        if (sum > max_sum)
            return 0;
        sq = (int)sqrt((float)left);
    }

    return sum && digit_sum(left) + sum == max_sum;
}

int main()
{
    int j, i, val;

    while (1) {
        scanf("%d", &val);
        if (!val)
            break;
        for (val++; !is_smith(val); val++);
        printf("%d\n", val);
    }

    return 0;
}

posted on 2010-02-27 15:29 糯米 阅读(863) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理