30/09/2018, 19:19
Viết ct tính tổng các ước của 1 số nguyên dương N 10^9
ai giúp e với ạ, thuật toán của em toàn bị quá thời gian
nhìn thì đơn giản nhưng tối ưu hóa nó k đc ạ
viết bằng C++ ạ
Bài liên quan
Tìm ước thì chạy đến sqrt(n) là dc rồi. Vì nếu a< sqrt(n) mà a là ước của n, thì n/a cũng là ước của n
nếu theo thuật toán đó thì với số 100 sai ngay
bạn còn cách nào khác không :(cry:
Sai sao dc. Nếu n là số chính phương thì sqrt(n) chỉ cộng 1 lần thôi, nhớ kt dk này là dc
Cách tốt hơn thì có thể dùng thuật toán pollar-rho để phân tích thừa số nguyên tố. Sau đó đung công thức tổng ước để tính. Nếu nhanh hơn nữa để phân tích thừa số nguyên tố có thể dùng elliptic sieve…
mình biết cách phân tích thừa số nguyên tố, nhưng không biết cách tính ước, bạn có thể chỉ rõ cho mình chút xíu đc không
phân tích ra số nguyên tố thì chỉ toàn là ước nguyên tố, ví dụ số 20 thì sẽ là 1+2+5+10
nhưng vẫn còn 4 nữa. mình kẹt chỗ này
nếu N= p1k1p2k2…
thì công thức tổng ước sẽ là: (p1k1+1-1)/(p1-1)*(p2k2+1-1)/(p2-1)…
Trong đó p1,p2… là thừa số nguyên tố, k1,k2… tương ứng là lũy thừa