diff options
author | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2017-08-13 00:42:13 +0700 |
---|---|---|
committer | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2017-08-13 00:42:13 +0700 |
commit | df20bbbebb8d5951607560d358c1a19388743113 (patch) | |
tree | ac91e25ccadd2c0de75494b72022c08046fffdd8 /others/other/lcm.c | |
parent | ebb579dd31a19a4d08a8e9aae97c5fc354bc3e8b (diff) | |
download | cp-df20bbbebb8d5951607560d358c1a19388743113.tar.gz |
Tài thầy
Diffstat (limited to 'others/other/lcm.c')
-rw-r--r-- | others/other/lcm.c | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/others/other/lcm.c b/others/other/lcm.c new file mode 100644 index 0000000..961599d --- /dev/null +++ b/others/other/lcm.c @@ -0,0 +1,59 @@ +#include <stdio.h> +#include <stdlib.h> + +#define ul unsigned long +#define LEN 1000001 +#define P_LEN 78498 + +ul PRIMES[P_LEN]; + +ul *psearch(ul key) +{ + ul lo = 0, hi = P_LEN, mid; + while (lo < hi) { + if (key < PRIMES[mid = (lo + hi) / 2]) + hi = mid; + else + lo = mid + 1; + } + return PRIMES + lo; +} + +void factorange(ul *d, ul prime, ul start, ul stop) +{ + ul i = 0; + for (; stop; i += stop /= prime); + for (start -= 1; start; i -= start /= prime); + *d *= i * 2 + 1; + *d %= 111539786; +} + +int main() +{ + FILE *fi = fopen("LCM.INP", "r"), *fo = fopen("LCM.OUT", "w"); + char t; + ul a, b, c = 0, d, *i = calloc(LEN, sizeof(ul)), *j; + + for (a = 2; a < 1001; a++) + if (!i[a]) { + for (b = a * a; b < LEN; b += a) + i[b] = 1; + PRIMES[c++] = a; + } + for (; a < LEN; a++) + if (!i[a]) + PRIMES[c++] = a; + free(i); + + fscanf(fi, "%hhd\n", &t); + for (; t--;) { + fscanf(fi, "%ld %ld\n", &a, &b); + j = psearch(b); + for (d = 1, i = PRIMES; i < j; factorange(&d, *i++, a, b)); + fprintf(fo, "%ld\n", d); + } + + fclose(fi); + fclose(fo); + return 0; +} |