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

Points: 0.01 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

bedao

Problem type

Allowed languages

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

Comments

Comments

Please read the guidelines before commenting.

-1

duyanh69 commented on Jan. 5, 2026, 2:04 p.m. ← edit 4 →

toi bi ngu

-3

vuonghoaitamdz9 commented on Sept. 1, 2025, 12:08 p.m.

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; }

lego21910 commented on Aug. 20, 2025, 3:38 p.m. ← edited →

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 commented on March 29, 2025, 8:11 a.m. ← edited →

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 commented on March 13, 2025, 2:22 a.m.

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

-1

danglebinhnguyen2014 commented on March 13, 2025, 2:20 a.m.

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

0

haianh11112013 commented on March 7, 2025, 3:04 a.m.

-6

chitxd commented on Feb. 25, 2025, 11:40 a.m.

bài này làm sao thế ạ e ac có 40 test

This comment is hidden due to too much negative feedback. Show it anyway.

0

NightilyFurrying commented on Feb. 24, 2025, 8:51 a.m. ← edited →

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 commented on March 7, 2025, 6:41 p.m.

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

-6

tuanmmg150 commented on Feb. 23, 2025, 1:58 p.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.

-19

hsgboiduong commented on Feb. 22, 2025, 1:26 p.m.

dùng thuật toán j v các bạn ạ

This comment is hidden due to too much negative feedback. Show it anyway.