hihocoder 1186

1186 : Coordinates

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

Give you two integers P and Q. Let all divisors(因子，约数) of P be X-coordinates. Let all divisors of Q be Y-coordinates(Y坐标).

For example, when P=6 and Q=2, we can get the coordinates (1,1) (1,2) (2,1) (2,2) (3,1) (3,2) (6,1) (6,2).

You should print all possible coordinates in the order which is first sorted by X-coordinate when coincides, sorted by Y-coordinate.

输入

One line with two integers P and Q(1 <= P, Q <= 10000).

输出

The output may contains several lines , each line with two integers X_i and Y_i, denoting the coordinates.

样例输入

6 2

 样例输出

1 1
1 2
2 1
2 2
3 1
3 2
6 1
6 2

 题目大意：

给定数字P,Q，求出所有P和Q的约数p,q能够组成的不重复数字对(p,q)

解题思路：

     本题中需要求出P,Q所有约数组成的数字对，因此我们需要先将P,Q两个数字所有的约数分别找出来，再依次组合后输出。求解一个数字P的所有约数，
可以依次枚举1..P分别进行检查是否能够被P整除，也可以降低复杂度只枚举1..sqrt(P)，具体实现可以参考如下伪代码：

 // 枚举 1.. P
p_count = 0
For i = 1 .. P
    If (P mod i == 0) Then
        p_divisors[p_count] = i
        p_count = p_count + 1
    End If
End For

// 枚举 1 .. sqrt(P)
p_count = 0
For i = 1 .. sqrt(P)
    If (P mod i == 0) Then
        p_divisors[p_count] = i
        p_count = p_count + 1
        If (P div i > i) Then
            // 这个判断语句的作用是为了防止当 P 为平方数时
            // 若（P div i >= i）则会将 sqrt(P) 重复加入约数中
            p_divisors[p_count] = P div i
            p_count = p_count + 1
        End If
    End If
End For
// 用这种方法得到的约数序列需要进行排序
Sort(p_divisors)


在得到p_divisors和q_divisors之后，再通过双重循环，即可将所有的数字对打印出来：

For i = 0 .. p_count - 1
    For j = 0 .. q_count - 1
        Output(p_divisors[i] + ' ' + q_divisors[j])
    End For
End For

到此，本题也就顺理解决。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;


int p_divisors[5005];
int q_divisors[5005];

int main(){
    int i, j, p, q, p_count = 0, q_count = 0;
    scanf("%d %d", &p, &q);
    
    for(i = 1; i <= p; i++){
        if(p % i == 0){
            p_divisors[p_count] = i;
            p_count++;
        }
    }
    
    for(i = 1; i <= q; i++){
        if(q % i == 0){
            q_divisors[q_count] = i;
            q_count++;
        }
    }
    /*
    for(int i = 1; i <= sqrt(p); i++){
        if(p % i == 0){
            p_divisors[p_count] = i;
            p_count++;
            if(p / i > i){
                p_divisors[p_count] = p / i;
                p_count++;
            }
        }
    }
    sort(p_divisors, p_divisors + p_count);
    
    for(int i = 1; i <= sqrt(q); i++){
        if(q % i == 0){
            q_divisors[q_count] = i;
            q_count++;
            if(q / i > i){
                q_divisors[q_count] = q / i;
                q_count++;
            }
        }
    }
    sort(q_divisors, q_divisors + q_count);*/



    for(i = 0; i < p_count; i++){
        for(j = 0; j < q_count; j++){
            printf("%d %d
", p_divisors[i], q_divisors[j]);
        }
    }
    
    return 0;
    
}