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[];
 int q_divisors[];

 int main(){
     int i, j, p, q, p_count = , q_count = ;
     scanf("%d %d", &p, &q);

     for(i = ; i <= p; i++){
         if(p % i == ){
             p_divisors[p_count] = i;
             p_count++;
         }
     }

     for(i = ; i <= q; i++){
         if(q % i == ){
             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 = ; i < p_count; i++){
         for(j = ; j < q_count; j++){
             printf("%d %d\n", p_divisors[i], q_divisors[j]);
         }
     }

     return ;

 }