hihoCoder 1186 : Coordinates（快速求因子【思維】）

題目連結：http://hihocoder.com/problemset/problem/1186

【中文題意】給你兩個整數p和q,讓所有p的因子作為x坐标，所有q的因子作為y坐标求出所有的點，先按x排序，後按y排序。

【思路分析】首先如果暴力求的話時間複雜度會達到O(n^2)。n<=10000。顯然暴力是不可以的，是以我們要想辦法來優化一下，開平方優化無疑是最好的選擇。

【AC代碼】

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

int a[],b[];
int main()
{
    int p,q;
    while(~scanf("%d%d",&p,&q))
    {
        int sum1=,sum2=;
        for(int i=;i*i<p;i++)
        {
            if(p%i==)
            {
                a[sum1++]=i;
                a[sum1++]=p/i;
            }
        }
        if((int)sqrt(p)*(int)sqrt(p)==p)
        {
            a[sum1++]=(int)sqrt(p);
        }
        for(int i=;i*i<q;i++)
        {
            if(q%i==)
            {
                b[sum2++]=i;
                b[sum2++]=q/i;
            }
        }
        if((int)sqrt(q)*(int)sqrt(q)==q)
        {
            b[sum2++]=(int)sqrt(q);
        }
        sort(a,a+sum1);
        sort(b,b+sum2);
        a[sum1]=;
        b[sum2]=;
        for(int i=;i<sum1;i++)
        {
            if(a[i]!=a[i+])
            {
                for(int j=;j<sum2;j++)
                {
                    if(b[j]!=b[j+])
                    {
                        printf("%d %d\n",a[i],b[j]);
                    }
                }
            }
        }
    }
    return ;
}