---
tags: VNOJ, THT , Sieve, Factorization , Combinatorics ,LeThanhMinh, Melonade, SPyofgame
title: 🌱 Lời giải bài Tin học trẻ 2021 - Vòng khu vực - Bảng B - Tập Số
author: Editorial-Slayers Team
license: Public domain
---
---
# 🌱 Lời giải bài Tin học trẻ 2021 - Vòng khu vực - Bảng B - Tập Số

>[color=pink] Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart:
###### 🔗 Link: [https://oj.vnoi.info/problem/tht21_kvb_fset](https://oj.vnoi.info/problem/tht21_kvb_fset)
###### 📌 Tags: `Sieving` ,`Factorization` ,`Combinatorics`.
###### 🛠 Work: At least 3 hours
###### 👤 Writer: @LeThanhMinh
###### 👤 Editor: @Melonade, @SPyofgame
###### 👥 Contributor: [@Editorial-Slayers Team](https://hackmd.io/@Editorial-Slayers)
###### 📋 Content:
[TOC]
____
## Nhận xét :label:
Ta phải nhận biết rằng khi là một số chính phương, thì chắc chắn lũy thừa của từng thừa số nguyên tố tạo nên nó phải là một số chẵn (đây là một dữ kiện rất quan trọng để có thể giải quyết bài toán).

:question: Vậy điều kiện để hai số nhân lại với nhau tạo ra số chính phương là gì ?

:bulb: 2 số nhân lại với nhau là số chính phương khi tích 2 số mà phân tích ra thì các thừa số nguyên tố đều có số mũ chẵn.

>[color=red] Ta lấy tích của số $2$ và $8$. Phân tích $2$ ra thừa số nguyên tố là $2^{1}$, phân tích $8$ ra thừa số nguyên tố là $2^{3}$; tích của $2$ và $8$ là $16$ phân tích ra thừa số nguyên tố là $2^{4}$ nhưng khi ta nén các số $2$ và $8$ lại bằng cách mod lũy thừa của các số nguyên tố cho $2$ thì nó tương tự như nhau thành $2^{1}$ và $2^{1}$; cũng đều tạo ra số chính phương (tương tự với cặp $4$, $16$ nén ra $2^{0}$ và $2^{0}$ ).
>
>*Nó tạo ra một mối quan hệ đối với các số nén lại và đưa về bài toán dễ hơn*: đếm số tập số thoả mãn các số nén trong tập số đó đôi một khác nhau.
>
Gọi $F(x)$ là số $x$ sau khi được nén, $F(y)$ là số $y$ sau khi được nén; dễ thấy nếu $x*y$ là số chính phương thì $F(x) = F(y)$. Vậy ta nhận xét rằng các tập số đúng đều phải có số sau khi nén hoàn toàn khác nhau; hay là các tập số đúng sẽ có $F(u) \neq F(v)$ với mọi $u\neq v$.

* Cách nén một số là ta phân tích ra thừa số nguyên tố phân biệt với $P_i$ là một trong những thừa số nguyên tố phân biệt được phân tích, có lũy thừa của nó là $x_i$ thì số đó nén lại sẽ có dạng $P_i^{x_i \text{ mod } 2}$ * $P_j^{x_j \text{ mod } 2}$ * ... * $P_k^{x_k \text{ mod } 2}$ (với $x$ $mod$ $y$ là số dư của $x$ khi chia cho $y$).

Ta nhận xét rằng các tập số đúng là các tập số mà các phần tử trong đó đôi một khác nhau, vì vậy với từng số nén ta cần đếm xem có bao nhiêu số nén ra nó và việc của chúng ta là với từng số nén ra số này ta phải chọn 1 số và bỏ vào tập hợp.

:bulb: Vậy bài toán giờ đã có hướng giải quyết bằng cách nén số rồi với mỗi số nén ta dùng mảng đếm $cnt_i$ nếu khi ta nén số $k$ ra $i$ ta tăng $cnt_i$ một đơn vị

:bulb: Với mỗi nhóm $u$ có $cnt_u + 1$ cách chọn, mà mỗi nhóm là độc lập nhau nên số dãy thỏa mãn sẽ là $res = (cnt_a + 1) * (cnt_b + 1) * ... * (cnt_c + 1)$ ;
## Ý tưởng :bulb:
Ta phải sàng nguyên tố sau đó chạy hết tất cả các số từ $1$ đến $n$, với mỗi số ta thực hiện thao tác nén số (phân tích ra thừa số nguyên tố rồi mod $2$ các số mũ của các thừa số nguyên tố đó). Với số $i$ ($1$ $\le$ $i$ $\le$ $n$) ta có số $j$ là số sau khi nén của $i$ ta chỉ cần tăng $cnt_j$ lên $1$.
Với phần tính kết quả ta chỉ cần tính tổ hợp với số nén là $i$ ta có thể chọn $1$ số nén lại ra $i$ hoặc không chọn số nào; hay có $cnt_i +1$ cách chọn với việc $+1$ là không chọn số nào trong $cnt_i$ số ,kết quả là tích của tất cả $cnt_i + 1$ với ($1$ $\le$ $i$ $\le$ $n$ ).
## Tối ưu thuật toán :thought_balloon:
>[color=green] Bài này code khá đơn giản nhưng quan trọng là ta phải nhận ra mối quan hệ của các số có cùng số nén.
>Bạn có thể đọc cách sàng nguyên tố, phân tích ra thừa số nguyên tố với độ phức tạp thấp tại [đây](https://vnoi.info/wiki/translate/he/Number-Theory-2.md).
____
## Code
> **Time:** $O(n \log n)$
> **Space:** $O(n )$
> **Algo:** Sieveing ,Factorization ,Combinatorics.
> [color=lightgreen]
:::success
:::spoiler code của LeThanhMinh

#include<bits/stdc++.h> 
using namespace std;
const long long MAXN = 1e6+7; // giới hạn của số trong tập hợp là 1e6
long long minprime[MAXN];
long long  n,m;
void sieve(long long n){
    minprime[1]=1;
    for(int i = 3 ; i*i<=n ; i++ ){
         if(minprime[i] == 0){
              for(int j = 2* i ; j<= n ; j+=i ){
                  minprime[j] = i;
              }
              minprime[i] = i;
         }
    }// minprime[i] là số nguyên tố nhỏ nhất mà i chia hết 
    for(int i = 1 ;i <= n ; i++){
         if(minprime[i] == 0){
            minprime[i] = i;
         }
         if(i%2==0){
            minprime[i] =2;
         }
    }
}
long long cnt[MAXN];
long long nenso(long long z){
    long long res = 1;
    if(z==1 ){
        return  1;
    }
    while(z>1){
        long long  mu = 0;
        long long  k=minprime[z];
        while(z % k == 0 && z>1){
            z/= k;
            mu ++;
        }// phân tích ra thừa số nguyên tố và số mũ
        if(mu %2 == 1){
              res*= k;
        }
    }
    return res;
}
int main(){
    cin>>n>>m;
    sieve(n+100); /// sàng số nguyên tố
    ll res = 1;
    for(int i = 1 ; i <= n ; i++){
        long long z= nenso(i);
        cnt[z] ++;
        // với mỗi số i từ 1 đến n ta cập nhật mảng đếm với số nén từ số i
    }
    for(int i = 1 ;i<= n ;i++){
        res *= (cnt[i] +1 ) % m ;
        res %= m;
    }
    cout<<res;
    return 0;
}

:::success
:::::
>[color=lightgreen] **Time:** $O(n \log \log n)$
> **Space:** $O(n )$
> **Algo:** Sieveing ,Factorization ,Combinatorics.
:::success
:::spoiler code của Spyofgame

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;
const int LIM = 1e6 + 16;

/// SPyofgame Linear Sieve
vector<int> prime, lpf;
void sieve(int n = LIM)
{
    prime.assign(1, 2);
    lpf.assign(n + 1, 2);
    prime.reserve(78555);

    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime.push_back(lpf[x] = x);
        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}

/// res = Product(p[i]^(f[i] mod 2))
int getMask(int x)
{
    int res = 1;
    while (x > 1)
    {
        /// p = prime factor
        /// f = max power of p in x
        int p = lpf[x], f = 0;
        do x /= p, ++f;
        while (x % p == 0);

        /// p[i] ^ (f[i] mod 2)
        if (f & 1) res *= p;
    }

    return res;
}

int cnt[LIM];
int solve(int n, int m)
{
    memset(cnt, 0, sizeof(cnt[0]) * (n + 1));
    for (int x = 1; x <= n; ++x)
        ++cnt[getMask(x)];

    ll res = 1;
    for (int x = 1; x <= n; ++x)
    {
        if (cnt[x] == 0) continue;
        res *= cnt[x] + 1; /// number of way to select
        res %= m;          ///  set of number having the same mask
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;

    sieve(n);
    cout << solve(n, m);
    return 0;
}

::::
_____
## Bonus

Bạn có thể giải bài này trong $O(n)$ không?