首页 > ACM题库 > HDU-杭电 > hdu 2441 ACM(Array Complicated Manipulation)-最小生成树-[解题报告]hoj
2014
01-26

hdu 2441 ACM(Array Complicated Manipulation)-最小生成树-[解题报告]hoj

ACM(Array Complicated Manipulation)

问题描述 :

Given an infinite array of integers 2,3,…. Now do some operations on it.

The operation is to choose a minimum number from the array which is never been chosen, then change the status of its multiples excluding itself, i.e remove the multiples of the chosen number if they are in the array , otherwise add it to the array.keep the order after change.

For instance, the first step, choose number 2, change the status of 4, 6, 8, 10… They are all removed from the array. The second step, choose 3, change the status of 6, 9, 12, 15…

Pay attention: 9 and 15 are removed from the array while 6 and 12 are added to the array.

输入:

Every line contains an integer n. The zero value for n indicates the end of input.

输出:

Every line contains an integer n. The zero value for n indicates the end of input.

样例输入:

2
30
90
0

样例输出:

yes
yes
no

Hint
The number n never has a prime factor greater than 13000000, but n may be extremely large.

打表规律猜想代码:

#include<stdio.h>
#include<string.h>
const int N=100;
int a[N];
bool p[N];

int main()
{
    memset(p,true,sizeof(p));
    for(int i=0;i<N;i++)
    a[i]=i;
    for(int j=2;j<N;j++)
    {
        if(p[j])
        {
            for(int k=2;j*k<N;k++)
            if(p[j*k])p[j*k]=false;
            else p[j*k]=true;
        }
        for(int i=2;i<N;i++)
        if(p[i])printf("%d ",a[i]);
        else printf("  ");
        printf("\n");
    }
    return 0;
}
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 65536
bool div(char *p,int n)
{
    char temp[1000];
    int i,sum=0,len=0;
    for(i=0; p[i]!=0; i++)
    {
        sum=sum*10+p[i]-'0';
        temp[len++]=sum/n+'0';
        sum%=n;
    }
    temp[len]=0;
    if(sum==0)
    {
        for(i=0; temp[i]=='0'; i++);
        strcpy(p,temp+i);
        return 1;
    }
    else return 0;
}
int main()
{
    bool num[MAX+1];
    int prime[MAX],len=0,i,j;
    double t=sqrt(MAX);
    memset(num,1,sizeof(num));
    for(i=2; i<t; i++)
    {
        if(num[i])
        {
            for(j=2; i*j<=MAX; j++)num[i*j]=0;
        }
    }
    for(i=2; i<=MAX; i++)
    {
        if(num[i])prime[len++]=i;
    }
    char str[1000];
    while(scanf("%s",str),strcmp(str,"0")!=0)
    {
        if(strcmp(str,"1")==0)
        {
            printf("no\n");
            continue;
        }
        int count;
        for(i=0; i<len; i++)
        {
            count=0;
            while(div(str,prime[i]))
            {
                count++;
                if(count>=2)break;
            }
            if(count>=2)break;
        }
        if(count>=2)printf("no\n");
        else printf("yes\n");
    }
    return 0;
}

 

解题参考:http://www.cnblogs.com/XDJjy/archive/2013/05/22/3092575.html


  1. 期待好久了还不出来啊?此片希望多点何坚的浪漫争女之趣,于震也缺少点浪漫史,给人有所木纳的感觉;另欠缺些名言名语的加载,因每个人看电影也想看到有水平的电影,从而也能学到一点水平,而不是看一部没水平的电影而学不到点学问,没人喜欢浪费时间去看电影的。此片与箭在

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

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  4. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!