AcWing 869. 试除法求约数
原题链接
简单
作者:
Lux_Lu
,
2019-08-28 08:59:49
,
所有人可见
,
阅读 1031
可以只遍历一半,另一半由x/i O(1)求
/*
reference:
translation:
solution:
trigger:
note:
*
record:
date:
2019.08.26
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
#define N 1000010
int n,tot;
int p[N];
bool ip[N];
inline void divide(int x){
mem(p,0);
tot=0;
for(int i=1;i*i<=x;++i){
if(x%i==0){
p[++tot]=i;
if(x/i!=i)
p[++tot]=x/i;
}
}
sort(p+1,p+tot+1);
rep(j,1,tot)
printf("%lld ",p[j]);
puts("");
}
#undef int
int main(){
#define int long long
rd(n);
while(n--){
int x;rd(x);
divide(x);
}
return 0;
}