diff options
author | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2016-10-08 09:56:43 +0700 |
---|---|---|
committer | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2016-10-08 09:56:43 +0700 |
commit | 2a7bc10f6c011d19fb3b0e73068f7e1a9c30ace0 (patch) | |
tree | 95190a32ec1c7098494849eea5a5ba6b53289585 /NTU/root.c | |
parent | 207cc2ae9893b0cdecd20119b9ede37f73cd4a1e (diff) | |
download | cp-2a7bc10f6c011d19fb3b0e73068f7e1a9c30ace0.tar.gz |
Initial commit
Diffstat (limited to 'NTU/root.c')
-rw-r--r-- | NTU/root.c | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/NTU/root.c b/NTU/root.c new file mode 100644 index 0000000..01b9b30 --- /dev/null +++ b/NTU/root.c @@ -0,0 +1,37 @@ +#include <stdio.h> +#include <stdlib.h> +#include <math.h> + +int cmp(const void *x, const void *y) +{ + return *(long *) x - *(long *) y; +} + +int main() +{ + short i; + long a[31622]; /* square root of 1 billion */ + for (i = 0; i < 31622; i++) { + a[i] = i + 1; + a[i] *= a[i]; + } + + short t; + scanf("%hd", &t); + + long *n = malloc(t * sizeof(long)); + for (i = 0; i < t; i++) + scanf("%ld", &n[i]); + + long foo; + for (i = 0; i < t; i++) { + foo = (long) sqrt(n[i]); + foo *= foo; + foo = (long *) bsearch(&foo, a, 31622, 4, cmp) - a; + while ((foo > 0) && (n[i] % a[foo])) + foo--; + printf("%hd %ld\n", foo + 1, n[i] / a[foo]); + } + + return 0; +} |