1186 : Coordinates
描述
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 Xi and Yi, 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 ; }