about summary refs log tree commit diff
path: root/others/other
diff options
context:
space:
mode:
authorRaphael McSinyx <vn.mcsinyx@gmail.com>2017-08-08 21:01:05 +0700
committerRaphael McSinyx <vn.mcsinyx@gmail.com>2017-08-08 21:01:05 +0700
commitc63bd23b97a4bbb0c7bd30c871ad7feaad344e0d (patch)
treea34d973e318ce5279d746b46ce5b8f90696ded92 /others/other
parent5cfeec0f11dbcff922fe5b1a1a17bccf4812852e (diff)
downloadcp-c63bd23b97a4bbb0c7bd30c871ad7feaad344e0d.tar.gz
Add others/other/maxnum.py
Diffstat (limited to 'others/other')
-rw-r--r--others/other/README.md23
-rwxr-xr-xothers/other/maxnum.py25
2 files changed, 48 insertions, 0 deletions
diff --git a/others/other/README.md b/others/other/README.md
index eb632cd..a61f45a 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -693,3 +693,26 @@ của một đoạn mã nguồn. Mỗi dòng chứa một câu lệnh có một
 |                                LANG.INP                                 |  LANG.OUT   |
 | ----------------------------------------------------------------------- | :---------: |
 | NEXT<br>JUMP 4 or 6<br>NEXT<br>JUMP 3<br>NEXT<br>JUMP 8<br>NEXT<br>NEXT | 2<br>5<br>7 |
+
+## Tìm số
+
+Cho hai số tự nhiên *n* và *p*. Tìm số *m* lớn nhất để *p<sup>m</sup>* là ước
+số của *n*!.
+
+### Dữ liệu
+
+Gồm hai số *n* và *p*.
+
+### Kết quả
+
+Số *m* tìm được.
+
+### Giới hạn
+
+*n*, *p* ≤ 30000, đảm bảo *m* > 0.
+
+### Ví dụ
+
+| MAXNUM.INP | MAXNUM.OUT |
+| :--------: | :--------: |
+|    7 3     |     2      |
diff --git a/others/other/maxnum.py b/others/other/maxnum.py
new file mode 100755
index 0000000..c3b8868
--- /dev/null
+++ b/others/other/maxnum.py
@@ -0,0 +1,25 @@
+#!/usr/bin/env python3
+PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
+          67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
+          139, 149, 151, 157, 163, 167, 173)
+
+
+def factor(x):
+    d = {}
+    for i in PRIMES:
+        if not x % i:
+            d[i] = d.get(i, 0) + 1
+            x //= i
+    if x > 1: d[x] = 1
+    return d
+
+
+with open('MAXNUM.INP') as f:
+    n, p, d = *map(int, f.readline().split()), {}
+
+for i in range(2, n + 1):
+    for k, v in factor(i).items():
+        d[k] = d.get(k, 0) + v
+
+with open('MAXNUM.OUT', 'w') as f:
+    print(min(d[k] // v for k, v in factor(p).items()), file=f)