Tìm Cặp Số Bạn Bè (amicable Pairs) - Programming - Dạy Nhau Học Trang chủ » Số Bạn Bè Là Gì » Tìm Cặp Số Bạn Bè (amicable Pairs) - Programming - Dạy Nhau Học Có thể bạn quan tâm Số Bạn Bè Pascal Số Bạn Bè Tối đa Trên Facebook Số Bạn Bè Tối đa Trên Zalo Số Bạn Bè Trong Pascal Số Bạn Bè Wiki Tìm cặp số bạn bè (amicable pairs) programming c buitrungbao (Bùi Trung Bảo) December 12, 2018, 5:04pm #1 Đề bài: Người dùng nhập n. Hãy tìm các số p, q (0 < p < q < n) sao cho tổng các ước số thực sự của p bằng q và tổng các ước số thực sự của q bằng p. Tìm một thuật toán hiệu quả khi n lớn Em dùng thuật toán 2 vòng lặp nên nó chạy rất lâu khi n lớn, có ai có ý tưởng thuật toán hiệu quả hơn không ạ? Bài code của em: https://drive.google.com/open?id=13p_0CnK3XCLs-N-HvPooRbAsvYKLcOGj #include <stdio.h> int tongUocSo (int a){ int sum = 0; for (int i = 1; i < a; i++) if (a % i == 0) sum += i; return sum; } void cau4(){ int n, flag = 1; printf("Nhap n: "); scanf("%d", &n); for (int i = 1; i < n; i++){ for (int j = i + 1; j < n; j++){ if (tongUocSo(i) == j && tongUocSo(j) == i){ if (i > j){ printf("p = %d\nq = %d\n", j, i); flag = 0; } else { printf("p = %d\nq = %d\n", i, j); flag = 0; } } } } if (flag == 1) printf("Khong ton tai p va q trong khoang 0 toi %d\n", n); } int main(){ cau4(); } Mong cao nhân chỉ giáo. Em cảm ơn. rogp10 (rogp10) December 12, 2018, 9:14am #2 Tính tổng ước thì cách nhanh nhất là thông qua phân tích thừa số nguyên tố do tổng ước có nhân tính (multiplicative) với các số nguyên tố cùng nhau. Và chỉ cần chia tới sqrt(n) thôi. 4 Likes noname00 (HK boy) December 12, 2018, 9:16am #3 n lớn thì tra bảng thôi Amicable numbers Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. (A proper divisor of a number is a positive factor of that number other than the number itself. For example, the proper divisors of 6 are 1, 2, and 3.) A pair of amicable numbers constitutes an aliquot sequence of period 2. A related concept is that of a perfect number, which is a number that equals the sum of its own proper divisors, in other words a number which forms ... 4 Likes Nguyen_Hoang_Long1 (Nguyễn Hoàng Long) December 12, 2018, 9:33am #4 Hàm tìm ước số thực sự bạn cho chạy tới a/2 thôi. I vs j cũng loại bớt thay vì cho chạy hết 2 Likes buitrungbao (Bùi Trung Bảo) December 12, 2018, 9:35am #5 i với j loại như thế nào vậy anh? buitrungbao (Bùi Trung Bảo) December 12, 2018, 9:37am #6 em hơi khó hiểu ạ phân tích thừa số nguyên tố là phép nhân mà làm sao thành tổng vậy anh noname00 (HK boy) December 12, 2018, 4:07pm #7 Nguyen_Hoang_Long1: a/2 Chỉ cần đến sqrt(a) thôi nhé. buitrungbao: i với j loại như thế nào vậy anh? Bạn chỉ cần kiểm tra lại tongUocSo(tongUocSo(i)) có bằng i hay không thôi. Do vậy vứt đi được vòng lặp j vô nghĩa. buitrungbao: phân tích thừa số nguyên tố là phép nhân mà làm sao thành tổng vậy anh Bạn đọc cmt này và tìm hiểu thêm trên google. Cần giúp tăng tốc bài toán hơn ạ! programming Một dạng quy nạp đấy c/m tổng ước của n bằng tích tổng ước các thừa số nguyên tố của n, hay S(p1^j1 * p2^j2 * …) = S(p1^j1) * S(p2^j2) * … với p1, p2… nguyên tố và đôi một khác nhau. Đầu tiên đương nhiên S(p1^j1) = S(p1^j1) rồi. Xét n’ = n * p_i^j_i với gcd(p_i, n) = 1 ta có d | n <=> p_i^k*d | p_i^k*n (với k = [0.. j_i]) => p_i^k*d | p_i^j_i*n. Tức là các ước của n’ có dạng p_i^k*d. Cộng lại: sigma(k=0..j_i) sigma(d | n) (p_i^k*d) = sigma(k=0..j_i) (p_i^k * sigma(d | n)(d)) = s… 4 Likes rogp10 (rogp10) November 27, 2019, 3:44pm #8 Để mình đọc lại đã rồi xong. Cách 1: Cho m1, m2 là ước của m; n1, n2 là ước của n. Nếu m1n1 = m2n2 thì m1/n2 = m2/n1 Vì nếu UCLN(m1, n2) != 1 thì mâu thuẫn, nên hai phân số đều tối giản. Vậy tử bằng tử, mẫu bằng mẫu, suy ra đpcm. Cách 2: Với m, n nguyên tố cùng nhau thì m’ | m => m’ | mn n’ | n => n’ | mn m’, n’ | mn <=> BCNN(m’, n’) | mn (định nghĩa) Nếu UCLN(m’, n’) != 1 thì UCLN(m, n) != 1 do tích = UCLN * BCNN nên tìm được song ánh {ước của m} x {ước của n} -> {ước của mn} là (m’, n’) -> m’n’ 3 Likes Tăng tốc bài toán tính tổng các của n (trừ n) Tìm các cách cắt khác nhau của hình chữ nhật Gio (Gió) December 12, 2018, 11:47am #9 Dùng sàng nguyên tố để chứa thông tin 1 thừa số nguyên tố của mảng f O(nloglogn) Các số có thể phân tích ra thừa số nguyên tố từ thông tin mảng f trong O(nlogn) dùng bảng lưu kết quả và kiểm tra O(n) ideone https://ideone.com/Clj1Lv n = int(input()) f = [0]*(n+1) for i in range(2,int(n**.5)+1): if f[i] == 0: # so nguyen to for j in range(i*i,n+1,i): f[j] = i def sumdiv(x): x_ = x d = {} while f[x] != 0: d[f[x]] = d.get(f[x],0)+1 x//=f[x] d[x] = d.get(x,0)+1 ans = 1 for k,v in d.items(): ans*=(k**(v+1)-1)//(k-1) return ans-x_ T = [ 0 if i<2 else sumdiv(i) for i in range(n+1)] for i in range(2,n+1): if T[i]!=i and i<=T[i]<=n and T[T[i]]==i: print(i,T[i]) 4 Likes tntxtnt () December 12, 2018, 12:54pm #10 sao ko tạo mảng sumdiv[n] thẳng theo kiểu sàng luôn, cho i chạy từ 1 tới n bước 1, j từ 2*i tới n bước i, gán sumdiv[j] += i cũng O(nlogn) (n/2 + n/3 + n/4 + n/5 +… +n/(n-1) + n/n = n(1/2 + 1/3 + 1/4 + 1/5 + … + 1/(n-1) + 1/n) = O(nlogn)) tạo cái sàng nguyên tố làm gì ko biết đúng ko sửa lại i 1…n j 2*i…n step i :V edit: n = 1e6 chạy mất 3.6s ko nhanh bằng 3s nhưng mà trong sáng hơn nhoa :V n = int(input()) sumdiv = [1]*(n+1) for i in range(2, n+1): for j in range(2*i, n+1, i): sumdiv[j] += i for p in range(1, n): q = sumdiv[p] if p < q < n and sumdiv[q] == p: print(p, q) 4 Likes rogp10 (rogp10) December 12, 2018, 1:44pm #11 C (chạy sàng full) n = 1e6 0.01s (page size) n = 2e6 0.05s n = 5e6 0.23s n = 1e7 0.6s n = 4e7 2.9s n = 1e8 TLE còn cơm gạo thì phải ntn. https://sech.me/ap/articles.html 4 Likes buitrungbao (Bùi Trung Bảo) December 13, 2018, 4:35am #12 Em làm theo cách của anh ra kết quả có vẻ đúng, anh xem giúp em còn chỗ nào thừa thải không ạ Code: #include <stdio.h> #include <math.h> int tongUocSo(int a) { int sum = 0; for (int i = 1; i < sqrt(a); i++) if (a % i == 0) { sum += i + a/i; } return sum - a; } void cau4() { int n, flag = 1; printf("Nhap n: "); scanf("%d", &n); for (int i = 1; i < n; i++) { if (tongUocSo(tongUocSo(i)) < tongUocSo(i) && tongUocSo(tongUocSo(i)) == i) { printf("p = %d\nq = %d\n\n", tongUocSo(tongUocSo(i)), tongUocSo(i)); flag = 0; } } if (flag == 1) printf("Khong ton tai p va q thoa man de bai\n"); } int main() { cau4(); } Những cách còn lại của mấy anh nâng cao quá, em mới sinh viên năm nhất thôi Thảo luận rôm rả vầy em học được nhiều thứ mới Cảm ơn mấy anh nhiều noname00 (HK boy) December 13, 2018, 5:41pm #13 for các ước thực sự, bạn for từ 2 đến sqrt(a), tức là for (int i = 2; i <= sqrt(a); i++) if (a % i == 0) { if (i * i == a) sum += i; // trường hợp này chỉ cần + 1 số, vì i == a / i else sum += i + a / i; // trường hợp này cần cộng 2 số, vì 2 số phân biệt } return sum + 1; // không cần - a nữa, vì ta chỉ kể các ước thực sự trong khoảng [2, a / 2] // nhưng ta cần + 1 vì 1 cũng là ước thực sự Bạn mới for đến < sqrt(a), như vậy sẽ làm mất đi ước căn của a (nếu a là số chính phương). Trong vòng for i trong void cau4(), bạn gọi tongUocSo(i) khá nhiều lần. Nên gán nó vào 1 biến nào đó để tránh tính đi tính lại nhiều lần. 4 Likes buitrungbao (Bùi Trung Bảo) December 12, 2018, 4:34pm #14 Hiểu rồi, hay quá anh ạ Tối rồi em đi ngủ đây, chúc anh ngủ ngon :v rogp10 (rogp10) November 23, 2019, 9:31am #15 Bài này mà tính tay bo thì dù có dùng sàng cũng 10^9 là bứt gân trong khi giới hạn hiện tại là 4*10^19 10^20. https://sech.me/boinc/Amicable/forum_thread.php?id=91 https://sech.me/boinc/Amicable/forum_thread.php?id=183 Kĩ thuật loại trừ: https://sech.me/ap/articles.html#a1 4 Likes Tan_Truong1 (Tân Trương) April 2, 2020, 3:04am #16 sao phải kèm điều kiện tongUocSo(tongUocSo(i)) < tongUocSo(i) vậy ạ, e không hiểu đoạn này lắm rogp10 (rogp10) April 2, 2020, 3:18am #17 Nếu không sẽ bị trùng, kiểu (a, b) với (b, a), hay (a, a) (số hoàn hảo). 3 Likes H1A4C3K (H1A4C3K) April 17, 2021, 4:21pm #18 code mình chạy ngon nha bạn nhập 10 000 vào chạy ổn dưới 0.5s. 100 000 có hơi lâu khoảng 7-8s gì đó #include <bits/stdc++.h> using namespace std; int main(){ int b = 0, c = 0, d; cin >> d; cout << "\n\n\n\n\n"; for(int a = 1; a <= d; ++a){ b = 0; c = 0; for(int i = 1; i < a; ++i){ if(a % i == 0){ b += i; } } for(int i = 1; i < b; ++i){ if(b % i == 0){ c += i; } } if(a == c && a < b){ cout << a << " and " << b << "\n"; } } } 1 Like noname00 (HK boy) April 17, 2021, 7:15pm #19 Code O(n^2) đâu có lợi gì đâu bạn. Chủ thớt muốn 1 thuật toán hiệu quả với số lớn để chạy trong khoảng 1-2s kìa. 1 Like rogp10 (rogp10) April 18, 2021, 8:58am #20 Code này đâu khác gì code ở đầu thớt đâu. 2 Likes DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » Số Bạn Bè Là Gì BABE - Số Bạn Bè - NTUCoder - Bài Tập Số Bạn Bè Và Số Hoàn Hảo - 123doc Ứng Dụng Web Tìm Kiếm "cặp Số Bạn Bè" (friend Numbers) Số Bạn Bè Là Gì Toán Học Tuổi Trẻ::: - CẶP SỐ BẠN BÈ Có Vẻ Như Hầu Hết Chúng Ta ... Bạn Bè Là Cần Thiết Nhưng Thế Nào Là “BẠN” Và Thế Nào Là “BÈ”? TRONG SỐ BẠN BÈ CỦA BẠN Tiếng Anh Là Gì - Tr-ex Cách ẩn Danh Sách Bạn Bè Trên Facebook điện Thoại, Máy Tính Danh Sách Hạn Chế Trên Facebook Là Gì? Cách Thêm, Xóa Khỏi Danh ... Chế Độ Bạn Của Bạn Bè Trên Facebook Là Gì, Cách Thiết Lập ...
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?