Bedao Regular Contest 21 - Số chín ước - VNOJ: VNOI Online Judge

Bài này thật sự rất HAY nhưng đối với nhiều bạn mới thì nó cũng rất KHÓ .

Mình đã AC bài này với 0.00 s và 2.1 MB : https://oj.vnoi.info/submission/9980343

• CẢNH BÁO SPOILER !!! Mình rất tâm huyết với post này đồng thời dù đã rất cố gắng nhưng ko thể tránh khỏi sai sót . Mong bạn đọc nếu có ý kiến thì hãy góp ý cho mình để cải thiện và cùng nhau phát triển tốt hơn . Rất cảm ơn bạn đã dành thời gian cho post của mình ạ ! Ý TƯỞNG NẾU BẠN NÀO MUỐN HIỂU RÕ THUẬT TOÁN MÌNH SỬ DỤNG! I. Đầu tiên , để tìm số lượng ước thì ta sẽ xài phương pháp phân tích thừa số nguyên tố - Gọi s là số cần kiểm tra - Gọi n1 , n2 , n3 , ... là thừa số nt của s - Gọi e1 , e2 , e3 , ... lần lượt là số mũ của các thừa số nt n1 , n2 , n3 , ... + Ở đây có 2 trường hợp để s có 9 ước ~ TH1 : 1 * 9 = 9 => (e1+1) * (e2+1) = (0+1) * (8+1) = 9 => s chỉ có 1 thừa số nguyên tố và số mũ là 8 VD : 2^8 , 3^8 , ... ~ TH2 : 3 * 3 = 9 => (e1+1) * (e2+1) = (2+1) * (2+1) = 9 => s có duy nhất 2 thừa số nguyên tố và cùng có số mũ là 2 VD : 2^2 * 3^2 , ... + Tóm lại , khi số s được phân tích ra thừa số nguyên tố có dạng : n1^8 hay n1^2 * n2^2 thì sẽ có đúng 9 ước số II. Tiếp theo , ta nhận thấy số có 9 ước là số chính phương x^2 = s bởi vì các e1 , e2 , ... đều là số chẵn : 8 và 2. Từ đây , ta thấy có thể sử dụng căn bậc 2 của s để tính toán dễ dàng hơn . - Gọi x là sqrt(s); - Để tiếp tục cần check x không phải là số nguyên tố vì nếu là số nguyên tố, s sẽ có dạng n1^1 ko thỏa đk đặt ra. + Giải thích về phần chính thuật toán : - Nếu s gần khoảng 10^18 , sqrt(s) khoảng 10^9 => Bởi vì đã dùng căn bậc 2 nên các e1 , e2 , en trong phân tích s sẽ chia 2 => Lúc này nếu s có 9 ước thì x = n1 * n2 hoặc n1^4 III. Cuối cùng là phần xử lí 2 trường hợp mình đã nêu trên - Ta vận dụng tricks trong ước số : nếu a * b = c thì a hoặc b luôn <= sqrt(c) - Theo đó sử dụng trong TH1 (n1 * n2) - Ta tạo 1 mảng primes chứa các snt <= sqrt(x) // Ở đây mình sài 40000 cho tròn - Duyệt các snt trong primes . Lưu snt đầu tiên x % snt == 0 trong firstPrimes rồi dừng loop - Từ đó ta chỉ cần kiểm tra n2 = (x / firstPrims) có phải là số nguyên tố ko ? !!! Nếu đúng là vậy ta in ra YES =))) - Nếu ko ta tiếp tục TH2 (n1^4) + LƯU Ý : - Sẽ có rất nhiều bạn lấy firstPrimes ^ 4 == x ? lên đúng ko =) - Thật ra cách này không sai nhưng nó có thể gây tràn số đặc biệt là trong C++ - NÊN mình khuyến khích sài cách chia sẽ tối ưu hơn ko gây tràn số khi chia xong 4 lần chỉ cần ktra x == 1 ? !!! Nếu x = 1 thì chắc chắn phải in ra YES rồi =))) +~+ ĐẾN ĐÂY RỒI NẾU KO IN RA YES THÌ CHẮC CHẮN LÀ NO RỒI VÌ KHÔNG THỎA MÃN ĐIỀU KIỆN NÀO CẢ :) CODE CHO CÁC BẠN THAM KHẢO Ở ĐÂY!

Nếu bạn sử dụng code của mình thì hãy để lại 1 upvote cho mình vì nó tạo ra động lực cho mình rất nhiều ạ!