POJ - 3993(数论)

迷南。 2022-06-09 08:12 108阅读 0赞

问题描述:

Any positive integer v can be written as p 1 a1\*p 2 a2\*...\*p n an where p i is a prime number and ai ≥ 0. For example: 24 = 2 3\*3 1.   
Pick any two prime numbers p 1 and p 2 where p 1 = p 2. Imagine a two dimensional plane where the powers of p 1 are plotted on the x-axis and the powers of p 2 on the y-axis. Now any number that can be written as p 1 a1\*p 2 a2 can be plotted on this plane at location (x, y) = (a 1, a 2). The figure on the right shows few examples where p 1 = 3 and p 2 = 2.   
![ce51e00139a3c5e2baad9e4adfb4de16_v_1503962455][]

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 pi ∈ S (each raised to a power (a  i ≥ 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 SA ![\\subset][subset] 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.

![e358bdeff8e79ab546b75646a4a0349e_v_1503962455][]

Input

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

Output

For each test case, print the following line:   
k. X:D   
Where k is the test case number (starting at one,) X is the minimum ordinal needed in a space that both A and B can be plotted in. D is the distance between these two points.

Sample Input

168 882
    770 792
    0 0

Sample Output

1. 3:4
    2. 5:6

题目题意:题目的题意可以抽象成为，题目给我们俩个数，让我们分别质因子分解，然后求出这个俩个数的总共的质因子种类的个数和质因子的指数的差的绝对值的和.应该明白了吧！也可以看代码理解我在说什么。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const int maxn=1e6+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    
    int abs(int a)
    {
        if (a<0) return -a;
        else return a;
    }
    void get_prime()//打素数表
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    
    int factor[1000][2],fcnt;
    void get_factor(int n)//质因子分解
    {
        memset (factor,0,sizeof (factor));
        fcnt=0;
        for (int i=0;i<cnt&&prime[i]*prime[i]<=n;i++) {
            if (n%prime[i]==0) {
                factor[fcnt][0]=prime[i];
                while (n%prime[i]==0) {
                    factor[fcnt][1]++;
                    n=n/prime[i];
                }
                fcnt++;
            }
        }
        if (n!=1) {
            factor[fcnt][0]=n;
            factor[fcnt++][1]=1;
        }
    }
    int main()
    {
        int n,m,icase=1;
        get_prime();
        while (scanf("%d%d",&n,&m)!=EOF) {
            if (n==0&&m==0) break;
            get_factor(n);
            int a[1000][2],fcnt2=fcnt;//保存第一个数的信息
            for (int i=0;i<fcnt2;i++) {
                a[i][0]=factor[i][0];
                a[i][1]=factor[i][1];
            }
            get_factor(m);
            int ans=0,res=0;
            for (int i=0;i<fcnt2;i++) {
                for (int j=0;j<fcnt;j++) {
                    if (a[i][0]==factor[j][0]) {//如果俩个质因子相同
                        ans++;//记录重复了多少个
                        res+=abs(a[i][1]-factor[j][1]);//就加上他们的差值的绝对值
                        a[i][1]=factor[j][1]=0;//然后把他们清零，避免后面重复加上了，
                        break;
                    }
                }
            }
            for (int i=0;i<fcnt2;i++)//分别加上自己独有的质因子的指数
                res+=a[i][1];
            for (int i=0;i<fcnt;i++)
                res+=factor[i][1];
            printf("%d. %d:%d\n",icase++,fcnt+fcnt2-ans,res);
    
        }
        return 0;
    }

[ce51e00139a3c5e2baad9e4adfb4de16_v_1503962455]: https://odzkskevi.qnssl.com/ce51e00139a3c5e2baad9e4adfb4de16?v=1503962455
[subset]: https://odzkskevi.qnssl.com/bbb18112d0caab2527947a927f70b4c7?v=1503962455
[e358bdeff8e79ab546b75646a4a0349e_v_1503962455]: https://odzkskevi.qnssl.com/e358bdeff8e79ab546b75646a4a0349e?v=1503962455