題目鏈接：http://hihocoder.com/PRoblemset/problem/1186
【中文題意】給你兩個整數(shù)p和q,讓所有p的因子作為x坐標(biāo)，所有q的因子作為y坐標(biāo)求出所有的點，先按x排序，后按y排序。 【思路分析】首先如果暴力求的話時間復(fù)雜度會達(dá)到O(n^2)。n<=10000。顯然暴力是不可以的，所以我們要想辦法來優(yōu)化一下，開平方優(yōu)化無疑是最好的選擇。 【AC代碼】
#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<map>using namespace std;int a[10005],b[10005];int main(){ int p,q; while(~scanf("%d%d",&p,&q)) { int sum1=0,sum2=0; for(int i=1;i*i<p;i++) { if(p%i==0) { a[sum1++]=i; a[sum1++]=p/i; } } if((int)sqrt(p)*(int)sqrt(p)==p) { a[sum1++]=(int)sqrt(p); } for(int i=1;i*i<q;i++) { if(q%i==0) { 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]=0; b[sum2]=0; for(int i=0;i<sum1;i++) { if(a[i]!=a[i+1]) { for(int j=0;j<sum2;j++) { if(b[j]!=b[j+1]) { printf("%d %d/n",a[i],b[j]); } } } } } return 0;}新聞熱點
疑難解答
