首页 > ACM题库 > HDU-杭电 > HDU 1405 The Last Practice-[解题报告] C++
2013
12-09

HDU 1405 The Last Practice-[解题报告] C++

The Last Practice

问题描述 :

Tomorrow is contest day, Are you all ready?
We have been training for 45 days, and all guys must be tired.But , you are so lucky comparing with many excellent boys who have no chance to attend the Province-Final.Now, your task is relaxing yourself and making the last practice. I guess that at least there are 2 problems which are easier than this problem.
what does this problem describe?
Give you a positive integer, please split it to some prime numbers, and you can got it through sample input and sample output.

输入:

Input file contains multiple test case, each case consists of a positive integer n(1<n<65536), one per line. a negative terminates the input, and it should not to be processed.

输出:

For each test case you should output its factor as sample output (prime factor must come forth ascending ), there is a blank line between outputs.

样例输入:

60
12
-1

样例输出:

Case 1.
2 2 3 1 5 1

Case 2.
2 2 3 1
Hint

60=2^2*3^1*5^1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
#define M 100000
bool visit[101000];
int prime[101000];
int num2[14000];
struct node
{
    int num;
    int a;
} unit[7000];
void table()
{
    memset(visit,true,sizeof(visit));
    int num = 0;
    for (int i = 2; i <= M; ++i)
    {
        if (visit[i] == true)
        {
            num++;
            prime[num] = i;
        }
        for (int j = 1; ((j <= num) && (i * prime[j] <= M));  ++j)
        {
            visit[i * prime[j]] = false;
            if (i % prime[j] == 0) break; //µã¾¦Ö®±Ê
        }
    }
}
/*
4
Case 1.
2 2
23

Case 2.
23 1
-1

*/
/*
4
Case 1.
2 2
23

Case 2.
23 1
-1
*/
int main()
{
    memset(prime, 0, sizeof(prime));
    table();
    int n;
    int i,j,k;
    int y=1;
    //for(int i=1;i<7000;i++)
    //printf("%d\n",prime[i]);
    for(i=1; i<7000; i++)
    {

        unit[i].a=prime[i];
        unit[i].num=0;
    }
    while(scanf("%d",&n),n>0)
    {

        if(y!=1)
        printf("\n");
        printf("Case %d.\n",y);
        //for(i=1;i<7000;i++)
        //printf("%d\n",unit[i].a);
        for(i=1; i<7000; i++)
        {
            unit[i].num=0;
        }
        for(i=1; i<7000; i++)
        {
            if(n<0)
                break;
            while(n%unit[i].a==0)
            {

                unit[i].num++;
                n=n/unit[i].a;
                //printf("%d %d %d\n",unit[i].a,n,unit[i].num);
            }

        }
        int t=0;
        for(i=1; i<7000; i++)
        {
            if(unit[i].num)
            {
                num2[t]=unit[i].a;
                num2[t+1]=unit[i].num;
                t=t+2;
            }
        }
        //printf("%d\n",t);

        for(i=0; i<t-1; i++)
        {
            printf("%d ",num2[i]);
        }
        printf("%d \n",num2[t-1]);
        //printf("\n");
        y++;
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/were__wolf/article/details/16370821


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测