thảo luận [Học Tập] Topic thuật toán
- Thread starter unknowpc90
- Start date
Rex_2k
Junior Member
Rex_2k
Junior Member
đúng r thím,em nghĩ là phải tách cái n ra prime xử lý r hợp lại mà em chưa nghĩ ra hợp kiểu gì cho đúng, link thì contest private nên ko có thím ơi
Rex_2k
Junior Member
chưa thím ơi, em dùng cái khác, em xin hướng cụ thể hơn xíu với thím
Tân Bí Tịt
Senior Member
Chỗ hàm calculate có vẻ sai. Cái for-loop đầu tiên để tính modulo cho num thì ok. Còn cái forloop thứ 2 tính modulo cho pow_it thì hog đúng. Nó sai về mặt ý nghĩa đó, a^p % n sẽ khác với (a % n)^(p % n) % n
Chỗ này nên lấy modulo cho num thôi, rồi sau đó loop trên từng kí tự của string pow_it
Rex_2k
Junior Member
để em thử lại xem sao
a^b % n == (a%n)^b % n thì phải
à chưa kể ko cần mũ b đâu mà mũ 1 số x nào đó < n thoy
Chỉ áp dụng được khi a và n nguyên tố cùng nhau.
Dùng định lý Euler: a ^ b mod n = a ^ (k*phi(n) +b') mod n = a ^ b' mod n
Trong đó phi(n) là số số nguyên tố cùng nhau với n và nhỏ hơn n.
Kân team
Senior Member
vậy thớt tạch là do tính pow_it % mod là sai nè. Phải tính thẳng với string b luôn. Viết thêm 1 hàm chia 2 cho chuỗi số nguyên vd half("123") = "61". Cơ mà chia như vậy hóa ra O(n^2) gì mất rồi
à như brint nói biến đổi b thành chuỗi nhị phân trước vậy là
Last edited:
Rex_2k
Junior Member
B range nó 10^10^5 lận thím, phân tích kiểu này sao tính nổi thím nhỉ, nó vượt quá kiểu long long r
trungpham90
Đã tốn tiền
nipetvn làm đúng rồi mà fen vẫn ko hiểu à. Thế thì bài này hơi quá tầm vs fen rồi.
Ví dụ:
a^ab = (a^a)^10*a^b
a^abc = ((a^a)^10*a^b)^10*a^c
....
Rồi cứ thế thôi, đi từ index 0 đến index cuối của string, cứ mỗi index thì ^10 số trước lên rồi nhân vs mũ của giá trị tại index đó.
Hàm mũ pow ở trên tôi giả sử là đã xử lý mod n bên trong rồi.
Ví dụ:
a^ab = (a^a)^10*a^b
a^abc = ((a^a)^10*a^b)^10*a^c
....
Rồi cứ thế thôi, đi từ index 0 đến index cuối của string, cứ mỗi index thì ^10 số trước lên rồi nhân vs mũ của giá trị tại index đó.
Java:
long result = 1;
long a = // value of string a mod n
for(int i = 0; i < b.length(); i++){
int val = b.charAt(i) - 'a';
result = pow(result, 10)*pow(a, val);
result %= n;
}
Last edited:
Kân team
Senior Member
ví dụ "1729"^"8954" % 100 đi (dấu " " là cho chuỗi)
lấy a % n theo kiểu từ từ như trên kia:
1 % 100 = 1
(1*10 + 7) % 100 = 17
(17*10 + 2) % 100 = 72
(72*10 + 9) % 100 = 29
vậy bài toán chuyển thành 29^"8954" % 100. 29 là số nguyên, 100 là số nguyên, "8954" là chuỗi.
Nhận thấy là
29^"8954"
= 29^8000 * 29^900 * 29^50 * 29^4
= 29^4 * 29^50 * 29^900 * 29^8000
= (29^1)^4 * (29^10)^5 * (29^100)^9 * (29^1000)^8
Như vậy có thể viết thành vòng lặp, ban đầu đặt a' = 29, rồi vòng lặp tiếp theo tính a' = a'^10 để tính 29^1, 29^10, 29^100, 29^1000. Số 4, 5, 9, 8 kia có thể lấy từ chuỗi "8954" theo chiều ngược lại.
pseudocode:
Swift:
func pow(a: str, b: str, n: int) -> int {
let res:int = 1
let a′:int = mod_str_int(a, n)
let b′:str = reverse_str(b)
for c:chr in b′ do {
let d:int = digit_chr_to_int(c)
res = res * mod_pow(a′, d, n) % n // tính (29^1)^4 * (29^10)^5 * (29^100)^9 * (29^1000)^8
a′ = mod_pow(a′, 10, n) // tính 29^1, 29^10, 29^100, 29^1000
}
return res
}
func mod_str_int(a: str, n: int) -> int { ... } // "1729" % 100 -> 29
func reverse_str(s: str) -> str { ... }
func digit_chr_to_int(c: chr, n: int) -> int { ... }
func mod_pow(a: int, b: int, n: int) -> int { ... }// edit res init value = 1 chứ ko phải = 0
Last edited:
vozer267
Senior Member
Đào lên nào là đào lên nào.
Câu này không nhớ bị hỏi ở đâu nhưng đơn giản nó thế này:
Đọc một dãy số ra chữ bằng tiếng Anh. Điều kiện: input bất kỳ số nào
Ví dụ:
Input: 1999
Output: One thousand nine hundred ninety nine
Input: 1021
Output: One thousand twenty one
Input: 101
Output: One hundred and one
Input: 11
Output: Eleven
Câu này không nhớ bị hỏi ở đâu nhưng đơn giản nó thế này:
Đọc một dãy số ra chữ bằng tiếng Anh. Điều kiện: input bất kỳ số nào
Ví dụ:
Input: 1999
Output: One thousand nine hundred ninety nine
Input: 1021
Output: One thousand twenty one
Input: 101
Output: One hundred and one
Input: 11
Output: Eleven
Lập Trình Viên Số Khổ
Senior Member
Ngày trước làm bài này rồi nhưng bằng tiếng việt
Lập Trình Viên Số Khổ
Senior Member
JavaScript:
function convertNumber(num){
let lookup =['Không','Một','Hai','Ba','Bốn','Năm','Sáu','Bảy','Tám','Chín'];
array = Array.from(num.toString());
X = array.map(item => lookup[item]).reverse();
for(let i = 0; i < X.length; i++){
let alt = ['','Nghìn','Triệu'];
if(i%3 == 0){
if(X[i] == 'Không') X[i] = alt[i/3]
else X[i]+= ' ' + alt[i/3];
}
if(i%3 == 1){
if(X[i] == 'Không') {
if(alt.includes(X[i-1])) X[i] = '';
else X[i] = 'Linh';
}
else if(X[i] == 'Một') X[i] = 'Mười';
else X[i]+= ' Mươi';
}
if(i%3 == 2) X[i]+= ' Trăm';
}
X = X.filter(item => item!=='');
return X.reverse().join(' ').replace(/Không Trăm Nghìn/,'').replace(/Không Trăm$/,'');
}
console.log(convertNumber(110200100));vozer267
Senior Member
Đề là tiếng Anh mà? Luật nó cũng khác nhau. Mà cuối cùng ông làm về ngôn ngữ gì thế? Sao chuyển qua JS rồi?
Lập Trình Viên Số Khổ
Senior Member
Làm tương tự nhau thôi, tui giờ chuyển sang học web javascript rồi, nay toàn học js mà
Similar threads
