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;
+}