Tài thầy

4 files changed, 213 insertions, 0 deletions

diff --git a/others/other/README.md b/others/other/README.md
index cb1a9da..fc88fd4 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -764,3 +764,94 @@ Một số nguyên là số lần xuất hiện của X trong S sau L lần bi�
 |       2      | 1051151A | 150A1011151A1051151A         |
 |       3      | 1041251A | 150A1011151A1051151A1041251A |
 
+## Nguyên tố tương đương
+
+Hai số tự nhiên được gọi là *Nguyên tố tương đương* nếu chúng có chung các ước
+số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các
+ước nguyên tố là 3 và 5.
+
+### Yêu cầu
+
+Xét các số từ *a* đến *b*, hãy đếm xem có bao nhiêu cặp số (*x*, *y*) mà *x* <
+*y* và *x*, *y* là nguyên tố tương đương.
+
+### Dữ liệu
+
+* Dòng đầu chứa số nguyên *T* là số bộ dữ liệu;
+* *T* dòng sau, mỗi dòng chứa hai số nguyên dương *a*, *b*.
+
+### Kết quả
+
+Gồm *T* dòng, mỗi dòng là số cặp số nguyên tố tương đương tương ứng với bộ dữ
+liệu.
+
+### Giới hạn
+
+* *T* ≤ 10;
+* *a* ≤ *b* ≤ 10<sub>6</sub>.
+
+### Ví dụ
+
+|      EP.INP      | EP.OUT |
+| ---------------- | :----: |
+| 2<br>1 5<br>1 10 | 1<br>4 |
+
+## Số dư
+
+Cho *n* số nguyên dương *a<sub>1</sub>*, *a<sub>2</sub>*, …, *a<sub>n</sub>*,
+trong đó tồn tại ít nhất một cặp sô khác nhau. Hãy tìm số nguyên dương *d* lớn
+nhất để *a<sub>1</sub>* mod *d* = *a<sub>2</sub>* mod *d* = … = *a<sub>n</sub>*.
+
+### Dữ liệu
+
+* Dòng đầu chứa số nguyên dương *n*;
+* Dòng thứ hai chứa *n* số nguyên dương *a<sub>1</sub>*, *a<sub>2</sub>*, …,
+  *a<sub>n</sub>*;
+
+### Kết quả
+
+Gồm một dòng chứa số nguyên dương *d* lớn nhất thỏa mãn điều kiện đề bài.
+
+### Giới hạn
+
+* *n* ≤ 100;
+* *a<sub>i</sub>* ≤ 10<sup>16</sup>.
+
+### Ví dụ
+
+| remain.inp | remain.out |
+| ---------- | :--------: |
+| 3<br>3 7 9 |      2     |
+
+## LCM
+
+Trong số học, bội số chung nhỏ nhất (tiếng Anh: *Least Common Multiple* hoặc
+*Lowest Common Multiple* (LCM)) của hai số nguyên *x* và *y* là số nguyên dương
+nhỏ nhất chia hết cho cả x và y.
+
+### Yêu cầu
+
+Cho hai số nguyên dương *a* và *b* (*a* ≤ *b*), hãy đếm số cặp số nguyên dương
+*x*, *y* sao cho LCM(*x*, *y*) = *a* × (*a*+1) × … × *b*.
+
+### Dữ liệu
+
+* Dòng đầu chứa số nguyên *T* là số bộ dữ liệu;
+* *T* dòng sau, mỗi dòng chứa hai số nguyên dương *a*, *b*.
+
+### Kết quả
+
+Gồm *T* dòng, mỗi dòng tương ứng với *a*, *b* của bộ dữ liệu vào là số cặp số
+nguyên dương thoả mãn yêu cầu đề bài. Vì kết quả có thể rất lớn, hãy đưa ra giá
+trị là phần dư khi chia cho 111539786.
+
+### Giới hạn
+
+* *T* ≤ 10;
+* *a* ≤ *b* ≤ 10<sup>6</sup>.
+
+### Ví dụ
+
+|     LCM.INP     | LCM.OUT |
+| --------------- | :-----: |
+| 2<br>2 3<br>5 5 | 9<br>3  |
diff --git a/others/other/ep.c b/others/other/ep.c
new file mode 100644
index 0000000..7a6b2a2
--- /dev/null
+++ b/others/other/ep.c
@@ -0,0 +1,52 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int cmp(const void *x, const void *y)
+{
+	long z = *(long *) x - *(long *) y;
+	if (z < 0)
+		return -1;
+	if (z)
+		return 1;
+	return 0;
+}
+
+int main()
+{
+	FILE *fi = fopen("EP.INP", "r"), *fo = fopen("EP.OUT", "w");
+	char t;
+	long a, b, c, p[1000001], q[1000001];
+	long long count;
+
+	for (a = 1; a < 1000001; a++) {
+		p[a] = 1;
+	}
+
+	for (a = 2; a < 1001; a++)
+		if (p[a] == 1)
+			for (b = a; b < 1000001; b += a)
+				p[b] *= a;
+
+	fscanf(fi, "%hhd\n", &t);
+	for (; t--;) {
+		fscanf(fi, "%ld %ld\n", &a, &b);
+		b -= a - 1;
+		memcpy(q, p + a, b * sizeof(long));
+		qsort(q, b, sizeof(long), cmp);
+		count = 0;
+
+		for (a = c = 1; a < b; a++)
+			if (q[a] != q[a - 1]) {
+				count += c * (c - 1) / 2;
+				c = 1;
+			} else {
+				c++;
+			}
+		fprintf(fo, "%Ld\n", count);
+	}
+
+	fclose(fi);
+	fclose(fo);
+	return 0;
+}
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;
+}
diff --git a/others/other/remain.py b/others/other/remain.py
new file mode 100755
index 0000000..a81da89
--- /dev/null
+++ b/others/other/remain.py
@@ -0,0 +1,11 @@
+#!/usr/bin/env python3
+from functools import reduce
+from math import gcd
+
+
+with open('remain.inp') as f:
+    f.readline()
+    s = set(map(int, f.readline().split()))
+
+with open('remain.out', 'w') as f:
+    print(abs(reduce(gcd, map(s.pop().__sub__, s))), file=f)