diff options
Diffstat (limited to 'others/other')
| -rw-r--r-- | others/other/README.md | 91 | ||||
| -rw-r--r-- | others/other/ep.c | 52 | ||||
| -rw-r--r-- | others/other/lcm.c | 59 | ||||
| -rwxr-xr-x | others/other/remain.py | 11 |
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) |