题目描述 Description
给出n和n个整数，希望你从小到大给他们排序
输入描述 Input Description
第一行一个正整数n
第二行n个用空格隔开的整数
输出描述 Output Description
输出仅一行，从小到大输出n个用空格隔开的整数
样例输入 Sample Input
3
3 1 2
样例输出 Sample Output
1 2 3
数据范围及提示 Data Size & Hint
1<=n<=100000首先要知道：最大公约数*最小公倍数=A×B；
代码如下：
#include<stdio.h>
#include<math.h>
int gcd(int x,int y)//找x,y的最大公约数
{
return (x%y==0?y:gcd(y,x%y));
}
int main()
{
int x,y;
while(~scanf("%d%d",&x,&y))
{
int p,q,cnt = 0,i;
for(i=1;i<10000;i++)
{
/*p和q的最大公约数（gcd）是x，最小公倍数（lcm）是y.那么p*q=x*y ,*/
if( (y*x)%i == 0 )/*如果，i能被y*x整除，则判断(y*x/i)和i的最大公约数是不是x*/
{
if(gcd(y*x/i,i) == x)
cnt++;
}
}
printf("%d
",cnt);
}
return 0;
}
分析：
p和q的最大公约数（gcd）是x，最小公倍数（lcm）是y
那么p*q=x*y
设p=x*i,q=x*j，i和j互质
则p*q=（x*i）*（x*j）=x*y，那就有i*j=y/x
我们可以枚举i，从i=1开始，直到i*i>y/x
如果i是y/x的因子
然后j=（y/x）/i
再判断i和j是否互质
因为每次得到的两个数中比较小的就是i，比较大的数是j，i是小于根号（y/x）的，j就是大于根号（y/x）因此不会重复计算，那算到一次，答案就累加2。
#include<iostream>
using namespace std;
int gcd(int x,int y)
{
return(x%y==0?y:gcd(y,x%y));
}
int main()
{
int x,y,ans=0;
cin>>x>>y;
if(y%x){
cout<<0;
return 0;
}
y=y/x;
for(int i=1; i*i<=y; i++)
{
if(y%i==0&&gcd(i,y/i)==1)
ans+=2;
}
cout<<ans<<endl;
}上面的那个分析，主要是为了得到代码中那个循环的条件，还有大神的这个GCD（），一句话明了。
我的gcd（）是这个样子的：
int gcd(int a,int b)//欧几里得 求最大公约数
{
if(a<b)
{
int t=a;
a=b;
b=t;
}
if(b==0) return a;
else return gcd(b,a%b);
}