11 Jan 2024

https://lqdoj.edu.vn/problem/dhbb23tc

Cho một số nguyên dương

$n$.

Yêu cầu: Tìm chữ số tận cùng khác 0 của

$[1,2,3,...,n]$. Trong đó kí hiệu

$[a_1,a_2,...,a_m]$ là bội chung nhỏ nhất của

$a_1,a_2,...,a_m$.

Dữ liệu:

• Gồm một số dòng, mỗi dòng là một số nguyên dương
  $n$.

Kết quả:

• Với mỗi dòng tương ứng, in ra kết quả tương ứng với
  $n$.

Giới hạn:

• $1\le t\le 5$.
• $1\le n\le {10}^6$.

Thời gian: 1000ms cho mỗi testcase.

Tiếp cận

Gọi

$lcm$ là giá trị của

$[1,2,3,...,n]$.
Trước tiên chúng ta sẽ tìm giá trị của

$lcm$. Dễ thấy

$lcm$ có thể rất lớn nên ta chỉ lưu nó dưới dạng phân tích của nó ra thừa số nguyên tố.
Đến đây chúng ta sẽ tìm cách loại bỏ các chữ số 0 tận cùng của

$lcm$. Vì mỗi cặp thừa số

$2$ và

$5$ sẽ cho ra tích bằng

$10$ nên ta nghĩ đến việc loại bỏ nhiều nhất các cặp số

$(2,5)$ từ các thừa số nguyên tố của

$lcm$. Ta không cần xét các lũy thừa của

$2$,

$5$ như

$4,8,16,25,125...$ vì nó đã được phân tích thành các lũy thừa của

$2$, của

$5$ rồi.
Việc cuối cùng là nhân các lũy thừa lại với nhau đồng thời mod

$10$.

1. Tính giá trị

$lcm$ dưới dạng thừa số nguyên tố

(Sách giáo khoa Toán 6 cũ tập 1, chương I. Ôn tập và bổ túc về số tự nhiên, §18. Bội chung nhỏ nhất, mục 2 trang 58): Muốn tìm BCNN (Bội chung nhỏ nhất) của hai hay nhiều số lớn hơn 1, ta thực hiện ba bước sau:

• Phân tích mỗi số ra thừa số nguyên tố.
• Chọn ra các thừa số nguyên tố chung và riêng.
• Lập tích các thừa số đã chọn, mỗi thừa số lấy với số mũ lớn nhất của nó. Tích đó là bội chung nhỏ nhất cần tìm.

Ta nghĩ đến hướng giải đầu tiên: gọi

$nt$ là mảng lưu các thừa số nguyên tố cùng với số mũ của nó. chạy 1 vòng lặp

$i$ từ

$1$ đến

$n$, với mỗi

$i$ ta phân tích nó ra thừa số nguyên tố. Sau đó cập nhật giá trị lớn nhất của mỗi thừa số nguyên tố trong mảng

$nt$.

const int N = 1e6 + 1;
int minPrime[N] = {};
unordered_map<int, int> nt;

void minprime()
{
    for (int i = 2; i * i < N; i++) {
        if (minPrime[i] == 0) {
            for (int j = i * i; j < N; j += i) {
                if (minPrime[j] == 0) {
                    minPrime[j] = i;
                }
            }
        }
    }
    for (int i = 2; i < N; i++) {
        if (minPrime[i] == 0) {
            minPrime[i] = i;
        }
    }
}

for (int i = 1; i <= n; i++)
{
    int x = i;
    unordered_map<int, int> ntx;
    while (x != 1)
        ntx[minPrime[x]]++,
        x /= minPrime[x];

    for (auto p : ntx)
        nt[p.first] = max(nt[p.first], ntx[p.first]);
}

Tuy nhiên, với cách làm trên sẽ dẫn đến quá thời gian quy định của đề bài, bởi với mỗi

$n$ ta phải chạy tối đa

${10}^6$ lần các phép sau:

• Phân tích thừa số nguyên tố bằng sàng Eratosthenes có độ phức tạp
  $O(\log n)$.
• Cập nhật các giá trị max sau mỗi lần phân tích số
  $i$ lại tốn xấp xỉ
  $\pi (x)=\frac{x}{\log (x)}$ phép tính. (Xem hàm tính số lượng số nguyên tố).
• Ta còn phải nhân các lũy thừa lại modulo
  $10$ theo đề bài.

Ta nghĩ đến một hướng khác:

Nhận thấy, ở cuối cùng ta chỉ cần những số mũ lớn nhất có thể của các thừa số.
Nhận xét: với một thừa số

$p$ và giới hạn

$n$, khi

$p$ càng lớn thì số mũ

$k$ cao nhất có thể của

$p$ (trong

$nt$) sẽ càng có thể lớn (Có thể xem và kiểm chứng ở đây. Link 1 Link 2). Lấy ví dụ:

$n=6,p=2\to k=2$ (nếu

$k=3$ thì

$p^k=2^3=8>n=6$).

$n=12,p=2\to k=3$.

$n=18,p=2\to k=4$.

Vì vậy, ta chỉ cần duyệt qua các tất cả các thừa số nguyên tố

$\le n$, với mỗi thừa số

$p$ ta tìm số mũ

$k$ lớn nhất sao cho

$p^k\le n$. Hàm

$cal$ để tính số mũ

$k$ này có độ phức tạp là

$O({\log }_{p}n)$. Sau đó ta gán số mũ lớn nhất cho mỗi thừa số trong

$nt$.

int cal(int p) // k lớn nhất p^k <= n
{
    int k = 0;
    long long t = p;
    while (t <= n) t *= p, k++;
    return k;
}

nt.clear(); // reset map sau mỗi lần nhập n

for (int p = 2; p <= n; p++)
    if (!prime[p])
        nt[p] = cal(p);

Cách làm này tối ưu thời gian đáng kể, bởi thay vì duyệt qua

${10}^6$ lần như cách trước, ta chỉ cần chạy tối đa khoảng

$\pi ({10}^6)\approx 78498$ lần hàm

$cal$ và như thế sẽ không bị quá thời gian.

Tối ưu 13 Jan 2024: Ta vẫn có thể tiếp tục tối ưu bằng cách với mỗi thừa số khác

$2$ và

$5$ ta lũy thừa và nhân thẳng vào đáp án, đỡ tốn không gian lưu trữ

$nt$ và đỡ tốn thời gian chạy 1 vòng lặp. Đến đây nếu làm theo cách này có thể bỏ qua bước 2 và 3, xuất ra đáp án. Code tham khảo nằm ở cuối trang.

2. Loại các thừa số 2 và 5

Bước này thì rất đơn giản. Vì

$2\ast 5=10\equiv 0(\mathrm{mod}10)$ nên ta loại bỏ từng cặp

$(2,5)$ từ

$nt$ cho đến khi không làm được nữa.

int t = min(nt[2], nt[5]);
nt[2] -= t; nt[5] -= t;

3. In ra đáp án

Viết một hàm

$expo$ trả về giá trị của

$a^b\mathrm{mod}c$.
Đáp án sẽ là

$\prod _{\mathrm{\forall }[p,q]\in nt}expo(p,q)\mathrm{mod}10.$

long long expo(long long a, long long b)
{
    if (b == 0) return 1;
    long long t = expo(a, b/2) % mod;
    t = t * t % mod;
    return t * (b % 2 ? a : 1) % mod;
}

long long ans = 1;

for (auto &[a, b] : nt)
    ans *= expo(a, b),
    ans %= mod;

cout << ans;

4. Code đầy đủ:

Thời gian: 398ms;
Bộ nhớ: 6.97mB.

#include <iostream>
#include <unordered_map>
#include <math.h>
using namespace std;

const int mod = 10;
const int N = 1e6 + 1; int minPrime[N]; bool prime[N];
int n; unordered_map<int, int> nt;

void sieve()
{
    prime[0] = prime[1] = 1;
    for (int i = 2; i * i < N; i++) if (prime[i] == 0)
        for (int j = i * i; j < N; j += i) prime[j] = 1;
}
void minprime()
{
    for (int i = 2; i * i < N; i++) if (minPrime[i] == 0)
        for (int j = i * i; j < N; j += i) if (minPrime[j] == 0) minPrime[j] = i;
    for (int i = 2; i < N; i++) if (minPrime[i] == 0) minPrime[i] = i;
}
long long expo(long long a, long long b)
{
    if (b == 0) return 1;
    long long t = expo(a, b/2) % mod;
    t = t * t % mod;
    return t * (b % 2 ? a : 1) % mod;
}

int cal(int p) // k lớn nhất p^k <= n
{
    int k = 0;
    long long t = p;
    while (t <= n) t *= p, k++;
    return k;
}

void solve()
{
    nt.clear();
    // pttsnt 1 -> n + lấy lcm
    for (int p = 2; p <= n; p++) if (!prime[p]) nt[p] = cal(p);
    // for (int i = 1; i <= n; i++)
    // {
    //     int x = i; unordered_map<int, int> ntx;
    //     while (x != 1) ntx[minPrime[x]]++, x /= minPrime[x];
    //     for (auto p : ntx) nt[p.first] = max(nt[p.first], ntx[p.first]);
    // }
    // loại các ts nhân với nhau ra tận cùng 0
    int t = min(nt[2], nt[5]);
    nt[2] -= t; nt[5] -= t;
    //nhân hàng đơn vị các ts còn lại, chỉ lấy cs đơn vị
    long long ans = 1;
    for (auto &[a, b] : nt)
        ans *= expo(a, b),
        ans %= mod;

    cout << ans;
}

int main()
{
    #ifndef ONLINE_JUDGE
    #else
    freopen("tc.inp", "r", stdin);
    freopen("tc.out", "w", stdout);
    #endif

    // minprime();
    sieve();

    short t; cin >> t;
    while (t --> 0) cin >> n, solve(), cout << '\n';
}
/*
xét pttsnt của 1 số n bất kì
n tăng dần ~ max các số mũ của ts tăng theo
chỉ cần duyệt qua các tsnt p, với mỗi ts p
tính k lớn nhất sao cho p^k | n
-> duyệt tối đa PI(1e6) ~= 78498 ts
*/

13/1/2024
Thời gian: 188ms;
Bộ nhớ: 4.25mB.

#include <iostream>
#include <math.h>
using namespace std;

const int mod = 10;
const int N = 1e6 + 1; bool prime[N];
int n;

void sieve()
{
    prime[0] = prime[1] = 1;
    for (int i = 2; i * i < N; i++) if (prime[i] == 0)
        for (int j = i * i; j < N; j += i) prime[j] = 1;
}
long long expo(long long a, long long b)
{
    if (b == 0) return 1;
    long long t = expo(a, b/2) % mod;
    t = t * t % mod;
    return t * (b % 2 ? a : 1) % mod;
}

int cal(int p) // k lớn nhất p^k <= n
{
    int k = 0; long long t = p;
    while (t <= n) t *= p, k++;
    return k;
}

void solve()
{
    long long ans = 1;
    // pttsnt 1 -> n + lấy lcm
    for (int p = 7; p <= n; p++)
        if (!prime[p]) (ans *= expo(p, cal(p))) %= mod;
    // xử lí ts 3, 2, 5
    long long t1 = cal(2), t2 = cal(5), t = min(t1, t2);
    ans *= expo(3, cal(3)) * expo(2, t1 - t) * expo(5, t2 - t);
    cout << ans % mod;
}

int main()
{
    #ifndef ONLINE_JUDGE
    #else
    freopen("tc.inp", "r", stdin);
    freopen("tc.out", "w", stdout);
    #endif

    sieve();

    while (cin >> n) solve(), cout << '\n';
}
/*
xét pttsnt của 1 số n bất kì
n tăng dần ~ max các số mũ của ts tăng theo
chỉ cần duyệt qua các tsnt p, với mỗi ts p
tính k lớn nhất sao cho p^k | n
-> duyệt tối đa PI(1e6) ~= 78498 ts
*/