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

2019-11-11 05:16:18

字体：大中小

来源：转载

供稿：网友

题目链接：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[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;}

上一篇：字符串问题（二）

下一篇：增大JVM PermGen space内存