首页 > ACM题库 > HDU-杭电 > HDU 3353-Not So Flat After All-最小生成树-[解题报告]HOJ
2014
03-16

HDU 3353-Not So Flat After All-最小生成树-[解题报告]HOJ

Not So Flat After All

问题描述 :

Any positive integer v can be written as p1 a1 * p2 a2 * . . . pnan where pi is a prime number and ai >= 0. For example: 24 = 23 * 31.
Pick any two prime numbers p1 and p2 where p1 <> p2. Imagine a two dimensional plane where the powers of p1 are plotted on the x-axis and the powers of p2 on the yaxis. Now any number that can be written as p1 a1 * p2 a2 can be plotted on this plane at location (x, y) = (a1, a2). The figure on the right shows few examples where p1 = 3 and p2 = 2.
Tiles of Tetris, NOT!

This idea can be extended for any N-Dimensional space where each of the N axes is assigned a unique prime number. Each N-Dimensional space has a unique set of primes. We call such set the Space Identification Set or S for short. |S| (the ordinal of S) is N.
Any number that can be expressed as a multiplication of piTiles of Tetris, NOT! S (each raised to a power (ai >= 0) can be plotted in this |S|-Dimensional space. The figure at the bottom illustrates this idea for N = 3 and S = {2, 3, 7}. Needless to say, any number that can be plotted on space A can also be plotted on space B as long as SATiles of Tetris, NOT! SB.
We define the distance between any two points in a given N-Dimensional space to be the sum of units traveled to get from one point to the other while following the grid lines (i.e. movement is always parallel to one of the axes.) For example, in the figure below, the distance between 168 and 882 is 4.
Given two positive integers, write a program that determines the minimum ordinal of a space where both numbers can be plotted in. The program also determines the distance between these two integers in that space.

Tiles of Tetris, NOT!

输入:

Your program will be tested on one or more test cases. Each test case is specified on a line with two positive integers (0 < A,B < 1, 000, 000) where A * B > 1.
The last line is made of two zeros.

输出:

Your program will be tested on one or more test cases. Each test case is specified on a line with two positive integers (0 < A,B < 1, 000, 000) where A * B > 1.
The last line is made of two zeros.

样例输入:

168 882
770 792
0 0

样例输出:

1. 3:4
2. 5:6

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string.h>
using namespace std;
#define MAXN 1000000
int prime[MAXN],num;
bool notprime[MAXN];
int pa[MAXN],ma[MAXN];
int pb[MAXN],mb[MAXN];
void PRIME()
{
    int i,j;
    num=0;
    memset(notprime,false,sizeof(notprime));
    for(i=2;i<MAXN;i++)
       if(!notprime[i])
       {
           prime[num++]=i;
           for(j=i+i;j<MAXN;j+=i)
             notprime[j]=true;
       }    
}    
int main()
{
    int a,b;
    int na,nb;
    int i,j,t;
    int iCase=0;
    PRIME();
    while(scanf("%d%d",&a,&b))
    {
        if(a==0&&b==0) break;
        iCase++;
        na=nb=0;
        for(i=0;i<num&&a>0;i++)
        {
            if(a%prime[i]==0)
            {
                t=0;
                while(a%prime[i]==0)
                {
                    t++;
                    a/=prime[i];
                }   
                pa[na]=prime[i];
                ma[na++]=t; 
            }    
        }  
        for(i=0;i<num&&b>0;i++)
        {
            if(b%prime[i]==0)
            {
                t=0;
                while(b%prime[i]==0)
                {
                    t++;
                    b/=prime[i];
                }    
                pb[nb]=prime[i];
                mb[nb++]=t;
            }    
        }  
        int X=0,D=0;    
        i=0;j=0;
        while(i<na&&j<nb)
        {
            if(pa[i]==pb[j])
            {
                X++;
                D+=abs(ma[i]-mb[j]);
                i++;
                j++;
            }
            else if(pa[i]<pb[j])
            {
                X++;
                D+=ma[i];
                i++;
            }       
            else
            {
                X++;
                D+=mb[j];
                j++;
            }     
        }   
        while(i==na&&j<nb)
        {
            X++;
            D+=mb[j];
            j++;
        }
        while(i<na&&j==nb)
        {
            X++;
            D+=ma[i];
            i++;
        }   
        printf("%d. %d:%d\n",iCase,X,D);      
    }    
    return 0;
}

参考:http://www.cnblogs.com/kuangbin/archive/2011/08/27/2155667.html


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?