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

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    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)

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