Bedao Regular Contest 21 - Số chín ước

Xem dạng PDF
Gửi bài giải
Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Số chín ước là số có chính xác ~9~ ước nguyên dương. Ví dụ:

  • Số ~36~ là một số chín ước vì ~36~ có ~9~ ước nguyên dương là ~1, 2, 3, 4, 6, 9, 12, 18~ và ~36~.
  • Số ~2006~ không phải là một số chín ước do ~2006~ chỉ có ~8~ ước nguyên dương là ~1, 2, 17, 34, 59, 118, 1003~ và ~2006~.

QioCass đang rất tò mò về số chín ước và muốn biết một số ~n~ có phải là số chín ước không? Các bạn hãy giúp QioCass trả lời câu hỏi nhé.

Input

  • Dòng đầu tiên gồm một số nguyên ~T (1 \le T \le 10)~ ~-~ Thể hiện số lượng số cần trả lời.

  • Dòng thứ hai gồm ~T~ số nguyên ~X_i (1 \le X_i \le 10^{18})~ ~-~ Thể hiện số thứ ~i~ cần trả lời.

Output

  • Gồm ~T~ dòng, in ra YES nếu ~X_i~ là số chín ước, ngược lại in ra NO.

Scoring

Subtask Điểm Giới hạn
1 ~10~ ~X_i \le 10^6~
2 ~30~ ~X_i \le 10^{12}~
3 ~60~ Không có ràng buộc gì thêm

Sample Input 1

6
36 256 144 10 6 2006

Sample Output 1

YES
YES
NO
NO
NO
NO

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -2
    vuonghoaitamdz9  đã bình luận lúc 1, Tháng 9, 2025, 12:08

    include<bits/stdc++.h>

    define ll long long

    define N int(1e6)

    using namespace std; bool check(ll n){ ll s=1; for (int i=2;ii<=n;i++){ int t=0; while(n%i==0){ t++; n/=i; } s=2t+1; } if (n>1) s=3; if (s==9) return true; return false; } int main(){ iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0); int t; ll x; cin>>t; for (int i=1;i<=t;i++){ cin>>x; ll m=sqrt(x); if (m*m==x&&check(m)) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; } return 0; }


  • 11
    lego21910  đã bình luận lúc 20, Tháng 8, 2025, 15:38 ← chỉnh sửa

    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 ạ!

    // Code by lego21910 (Huy)
#include <iostream>
#include <cmath>
#include <bitset>

#define MAX 40000
using namespace std;
bitset<MAX+5> bs;
int primeFilters[MAX+5];

bool isPrime(int &n)
{
    if(n<2)
        return false;
    for(int i = 2 ; i * i <= n ; i++)
        if(n%i==0)
            return false;
    return true;
}

void sieve()
{
    for(int i = 2 ; i <= MAX ; i++)
        bs[i] = 1;
    for(int i = 2 ; i * i <= MAX ; i++)
        if(bs[i])
            for(int f = i * i ; f <= MAX ; f+=i)
                bs[f] = 0;
    int idx = 0;
    for(int i = 2 ; i <= MAX ; i++)
        if(bs[i])
            primeFilters[idx++] = i;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    sieve();
    int q;
    cin>>q;
    while(q--)
    {
        long long rn;
        bool isValid = false;
        cin>>rn;
        int n = sqrt(rn);
        if(1LL * n * n == rn && !isPrime(n))
        {
            int firstPrimeFactor = 0;
            for(int i = 0 ; i < MAX ; i++)
            {
                if(n % primeFilters[i] == 0)
                {
                   firstPrimeFactor = primeFilters[i];
                   break;
                }
            }
            int remains = n / firstPrimeFactor;
            if(isPrime(remains) && remains != firstPrimeFactor)
            {
                isValid = true;
            }
            else 
            {
                for(int i = 0 ; i < 4 ; i++)
                {
                    n /= firstPrimeFactor;
                }
                isValid = (n==1);
            }
        }
        cout << ((isValid) ? "YES\n" : "NO\n");
    }
    return 0;
}

  • 0
    QuanIsReal  đã bình luận lúc 29, Tháng 3, 2025, 8:11 ← chỉnh sửa

    các cao nhân chỉ mình giải bài này với, mình chỉ ăn được 2 subs đầu!


  • 2
    danglebinhnguyen2014  đã bình luận lúc 13, Tháng 3, 2025, 2:22

    https://ideone.com/XhSTEI Bài văn tự cổ


  • -1
    danglebinhnguyen2014  đã bình luận lúc 13, Tháng 3, 2025, 2:20

    https://ideone.com/H1vM6n Bài ảo thuật giáng sinh


  • -1
    haianh11112013  đã bình luận lúc 7, Tháng 3, 2025, 3:04

    https://chatgpt.com/c/67ca59a9-74c4-800b-8027-320a8207bf48


  • -6
    chitxd  đã bình luận lúc 25, Tháng 2, 2025, 11:40

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 0
    NightilyFurrying  đã bình luận lúc 24, Tháng 2, 2025, 8:51 ← chỉnh sửa

    Muốn dài dòng thì làm Prime Factorization. Lên mạng kiếm cách để biết một số có bao nhiêu ước để tìm hiểu thêm. Tính trả lời cái bình luận kia mà nó post qua đây luôn rồi


    • 0
      cucodethoi  đã bình luận lúc 7, Tháng 3, 2025, 18:41

      e chỉ ac đc 40test th ạ a cho e xin code mẫu với ạ


  • -6
    tuanmmg150  đã bình luận lúc 23, Tháng 2, 2025, 13:58 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -19
    hsgboiduong  đã bình luận lúc 22, Tháng 2, 2025, 13:26

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.