diff options
Diffstat (limited to 'NTU')
-rw-r--r-- | NTU/README.md | 3 | ||||
-rw-r--r-- | NTU/TutOnEqua.c | 55 | ||||
-rw-r--r-- | NTU/luth2.c | 55 |
3 files changed, 112 insertions, 1 deletions
diff --git a/NTU/README.md b/NTU/README.md index 345342e..8261d6c 100644 --- a/NTU/README.md +++ b/NTU/README.md @@ -3,7 +3,7 @@ - [x] pali: [Số Palindrome](http://laptrinh.ntu.edu.vn/Problem/Details/41) - [x] gacho: [Gà và chó](http://laptrinh.ntu.edu.vn/Problem/Details/116) - [x] luth: [Lũy thừa](http://laptrinh.ntu.edu.vn/Problem/Details/1156) -- [ ] luth2: [Lũy thừa 2](http://laptrinh.ntu.edu.vn/Problem/Details/2240) +- [x] luth2: [Lũy thừa 2](http://laptrinh.ntu.edu.vn/Problem/Details/2240) - [x] writer: [Robot đánh chữ](http://laptrinh.ntu.edu.vn/Problem/Details/3255) - [x] ngto4: [Tổng nguyên tố](http://laptrinh.ntu.edu.vn/Problem/Details/3256) - [x] demso0: [Đếm số không bên phải](http://laptrinh.ntu.edu.vn/Problem/Details/3330) @@ -27,3 +27,4 @@ - [x] chenhlech: [Chênh lệch](http://laptrinh.ntu.edu.vn/Problem/Details/5574) - [ ] editpic: [Chỉnh sửa ảnh](http://laptrinh.ntu.edu.vn/Problem/Details/5588) - [ ] cntpalin: [Đếm số Palindrome](http://laptrinh.ntu.edu.vn/Problem/Details/5600) +- [x] TutOnEqua: [Tutoring on equations](http://laptrinh.ntu.edu.vn/Problem/Details/5606) diff --git a/NTU/TutOnEqua.c b/NTU/TutOnEqua.c new file mode 100644 index 0000000..84cec70 --- /dev/null +++ b/NTU/TutOnEqua.c @@ -0,0 +1,55 @@ +#include <stdio.h> + +#define abs(x) (x < 0) ? -x : x + +int gcd(int a, int b) +{ + int c; + + while (b) { + c = a % b; + a = b; + b = c; + } + + return a; +} + +int main() +{ + int a, b, c, i, j, k, l, m, n, t; + char solutions[201][100]; + + scanf("%d", &t); + for (i = t; i; i--) { + for (k = 0; k < 201; k++) + for (l = 0; l < 100; l++) + solutions[k][l] = 0; + + scanf("%d", &n); + for (j = n; j; j--) { + scanf("%d %d", &a, &b); + if (a) { + c = gcd(a, b); + + if (a * b < 0) + a = -abs(a / c) + 100; + else + a = abs(a / c) + 100; + b = abs(b / c) - 1; + + solutions[a][b] = 1; + } + } + + m = 0; + for (j = 0; j < 201; j++) + for (k = 0; k < 100; k++) + if (solutions[j][k]) + m++; + + printf("%d\n", m); + } + + return 0; +} diff --git a/NTU/luth2.c b/NTU/luth2.c new file mode 100644 index 0000000..46bd99a --- /dev/null +++ b/NTU/luth2.c @@ -0,0 +1,55 @@ +#include <stdio.h> + +long long modinv(long a, long b) +{ + /* From: http://rosettacode.org/wiki/Modular_inverse#C */ + + long long t = 0, nt = 1, r = b, nr = a % b, q, tmp; + + while (nr) { + q = r / nr; + + tmp = nt; + nt = t - q * nt; + t = tmp; + + tmp = nr; + nr = r - q * nr; + r = tmp; + } + + return (t < 0) ? t + b : t; +} + +long powmod(long a, long b, long k) +{ + if (b == 1) + return a; + + long long p = powmod(a, b / 2, k); + p = (b % 2) ? p * p * a % k : p * p % k; + + return p; +} + +int main() +{ + short t, i; + long a, b, k, j; + long long c = 1; + + scanf("%hd", &t); + + for (i = t; i; i--) { + scanf("%ld %ld %ld", &a, &b, &k); + + if (b < 0) { + a = modinv(a, k) % k; + b = -b; + } + + printf("%ld\n", (b) ? powmod(a, b, k) : 1); + } + + return 0; +} |