Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.

Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!

Coding Challenge #5

Coding Challenge #5 có tên là Vô hạn. Đây là bài toán yêu cầu các thí sinh sử dụng nhiều kỹ năng số học để xử lý. Bài toán Vô hạn đã được 392 thí sinh thử sức và có 36 lời giải xuất sắc đạt được số điểm tối đa.

Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi 2 lời giải xuất sắc do bạn Nguyễn Hoàng Minh (lời giải 1) và Lê Minh Tuấn (lời giải 2) biên soạn.

Đề bài

Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.

Cho ~\mathcal{T}~ câu hỏi có dạng sau:

• Cho số nguyên dương ~n~, đếm số cặp số nguyên ~a, b~ thỏa ~1 \leq a, b \leq n~ và ~\frac{a}{b}~ là một số thập phân vô hạn.

Giới hạn:

• ~1 \leq \mathcal{T} \leq 10~
• ~1 \leq n \leq 10^{12}~

Lời giải 1

Subtask 1

Giới hạn: ~1 \leq n \leq {10}^{3}~

Ý Tưởng

• Một phân số ~\frac{a}{b}~ (với ~a~ và ~b~ là số nguyên dương) có thể được biểu diễn bằng số thập phân hữu hạn nếu như tồn tại hai số nguyên không âm ~k~ và ~e~ sao cho:

• Nếu ta đặt ~\frac{x}{y}~ là phân số tối giản bằng với ~\frac{a}{b}~ (tức ~\gcd(x, y) = 1~ và ~\frac{x}{y} = \frac{a}{b}~), điều kiện trên sẽ tương đương với việc tồn tại các số nguyên không âm ~c~, ~k~ và ~e~ sao cho:

Vì ~{10}^e~ không thể chứa ước nguyên tố ngoài ~2~ và ~5~, ~y~ (và ~c~ được chọn) cũng phải thỏa mãn điều kiện tương tự (~1~).

• Mặt khác, nếu ~y~ không chứa ước nguyên ngoài ~2~ và ~5~ thì ~y~ có thể được viết dưới dạng ~2^{u} \cdot 5^{v}~ với ~u~ và ~v~ là hai số nguyên không âm. Khi này, ta có thể đặt ~e = \max(u, v)~, ~c = 2^{e - u} \cdot 5^{e - v}~, và ~k = x \cdot c~, ta nhận thấy:

Vì thế ~\frac{a}{b}~ có thể được biểu diễn bằng số thập phân hữu hạn (~2~).

• Từ (~1~) và (~2~), ta thấy được rằng phân số ~\frac{a}{b}~ là một số thập phân hữu hạn nếu như mẫu số của phân số tối giản thu được từ việc rút gọn ~\frac{a}{b}~ không chứa bất kì một ước số nguyên tố nào ngoài ~2~ và ~5~.
  • Với giới hạn của subtask 1, chúng ta có thể đếm số lượng phân số là số thập phân hữu hạn trong thời gian cho phép bằng cách duyệt qua mọi cặp số nguyên dương ~(a, b)~ (~1 \leq a, b \leq n~) và thực hiện kiểm tra như trên.
  • Số lượng cặp số nguyên dương ~(a, b)~ (~1 \leq a, b \leq n~) mà ~\frac{a}{b}~ là số thập phân vô hạn bằng tổng số ~n^2~ cặp trừ đi số lượng các phân số cho kết quả hữu hạn trên.

Độ Phức Tạp

• Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O(t \cdot n^2 \cdot \log(n))~.
  • Chúng ta cần duyệt qua ~n^2~ cặp số; và
  • Với mỗi cặp số ~(a, b)~, chúng ta có thể:
    • xác định phân số tối giản tương đương trong ~O(\log n)~ bằng cách chia tử và mẫu với ước chung lớn nhất của chúng; và
    • xác định mẫu có chứa ước nguyên tố ngoài ~2~ và ~5~ bằng cách rút một trong hai ước nguyên tố này ra cho đến khi không thể thực hiện được nữa (khi này, phân số sẽ là một số thập phân hữu hạn nếu số được rút gọn bằng một; và một số thập phân vô hạn trong trường hợp còn lại). Chúng ta sẽ có thể phải thực hiện ~O(\log_2(n) + \log_5(n)) = \log(n)~ bước rút ước số ra.
• Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(1)~.

Code Minh Họa

#include <bits/stdc++.h>
using namespace std;

int countFractions(const int n) {
    int result = n * n;
    for (int a = 1, b = 1, d = 1, g = 1; a <= n; ++a)
        for (b = 1; b <= n; ++b) {
            g = __gcd(a, b);
            d = b / g;
            for (; !(d & 1); d >>= 1);
            for (; d % 5 == 0; d /= 5);
            if (d == 1)
                --result;
        }
    return result;
}

signed main() {
    int t = 0, n = 0;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> t;

    for (int i = 1; i <= t; ++i) {
        cin >> n;
        cout << countFractions(n) << '\n';
    }

    return 0;
}

Subtask 2

Giới hạn: ~1 \leq n \leq {10}^{6}~

Ý Tưởng

• Giới hạn của subtask 2 không cho phép chúng ta duyệt qua mọi phân số như subtask 1 nữa nhưng vẫn cho phép chúng ta có thể duyệt qua mọi giá trị mà tử số hoặc mẫu số có thể có.
• Với một phân số ~\frac{a}{b}~ (~1 \leq a, b \leq n~ và ~a, b~ là số nguyên), ta nhận thấy rằng để ~\frac{a}{b}~ là một số thập phân hữu hạn thì với mọi lũy thừa ~p^z~ (~z \in \mathbb{N}~) của một số nguyên tố ~p~ bất kì khác ~2~ và ~5~, nếu mẫu số ~b~ chia hết cho ~p^z~ thì ~a~ cũng phải chia hết cho ~p^z~ bởi như vậy, ta mới triệt tiêu được ước số nguyên tố khác ~2~ và ~5~ khỏi mẫu khi rút gọn phân số ~\frac{a}{b}~ thành phân số tối giản.

với ~\mathbb{P}~ là tập hợp các số nguyên tố.

• Một cách tổng quát hơn, nếu ta đặt ~b = 2^u \cdot 5^v \cdot w~ với ~u~ và ~v~ là số tự nhiên, và ~w~ là số tự nhiên không chia hết cho ~2~ và ~5~, thì ta có ~a = w \cdot s~ với ~s~ là số nguyên dương sao cho ~1 \leq a \leq n~. Vì vậy, với một số tự nhiên ~b~ xác định là mẫu số ~(1 \leq b \leq n)~, ta có thể chọn ~\lfloor \frac{n}{w} \rfloor~ giá trị hợp lệ khác nhau cho ~a~ bởi ~1 \leq s~ và ~w \cdot s \leq n \Rightarrow s \leq \frac{n}{w}~.
• Dựa trên quan sát này, ta có thể đếm số lượng phân số là số thập phân hữu hạn bằng cách duyệt qua mọi mẫu số ~b~ (từ ~1~ tới ~n~), xác định thành phần ~w~ được định nghĩa như trên và tính tổng các giá trị ~\lfloor \frac{n}{w} \rfloor~.

Độ Phức Tạp

• Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O(t \cdot n \cdot \log(n))~.
  • Chúng ta cần duyệt qua ~n~ mẫu số; và
  • Với mỗi mẫu số ~b~, chúng ta sẽ có thể phải thực hiện ~O(\log_2(n) + \log_5(n)) = \log(n)~ bước rút ước số ra khỏi ~b~ để xác định ~w~.
• Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(1)~.

Code Minh Họa

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1E9 + 7;

int countFractions(const int n) {
    long long result = 1LL * n * n;
    for (int a = 0, b = 1; b <= n; ++b) {
        for (a = b; !(a & 1); a >>= 1);
        for (; a % 5 == 0; a /= 5);
        result -= n / a;
    }
    return result % MOD;
}

signed main() {
    int t = 0, n = 0;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> t;

    for (int i = 1; i <= t; ++i) {
        cin >> n;
        cout << countFractions(n) << '\n';
    }

    return 0;
}

Subtask 3

Giới hạn: ~1 \leq n \leq {10}^{12}~

Ý Tưởng

• Giới hạn của subtask 3 không cho phép chúng ta duyệt qua mọi mẫu số như subtask 2. Tuy nhiên, ta có thể duyệt qua tất cả thành phần ~2^u \cdot 5^v~ khác nhau trong mẫu số (được đề cập trong subtask 2). Cụ thể hơn, ta có ~O(\log_2 n \cdot \log_5 n)~ trường hợp khác nhau bởi điều kiện ~2^u \cdot 5^v \leq n~ phải thỏa:
  • ~u~ có thể đạt giá trị lớn nhất khi ~v = 0~ ~\Rightarrow~ ~2^u \leq n~ hay ~u \leq \log_2 n~ Vì ~u \geq 0~, ~u~ có thể có ~O(\log_2 n)~ giá trị khác nhau;
  • Tương tự, ~v~ có thể đạt giá trị lớn nhất khi ~u = 0~ ~\Rightarrow~ ~5^v \leq n~ hay ~v \leq \log_5 n~ Vì ~v \geq 0~, ~v~ có thể có ~O(\log_5 n)~ giá trị khác nhau.

• Để đếm số lượng phân số là số thập phân hữu hạn, với mỗi thành phần ~2^u \cdot 5^v~, ta cần đếm số lượng cặp số ~(s, w)~ đại diện cho phân số ~\frac{s \cdot w}{2^u \cdot 5^v \cdot w}~ sao cho tất cả điều kiện sau thỏa:

  • ~\gcd(w, 10) = 1~ (tức ~2 \nmid w~ và ~5 \nmid w~): ~w~ không chia hết cho ~2~ và ~5~;
  • ~1 \leq s \leq \lfloor \frac{n}{w} \rfloor~ (bởi ~1 \leq s \cdot w \leq n~);
  • ~1 \leq w \leq \lfloor \frac{n}{2^u \cdot 5^v} \rfloor~ (bởi ~1 \leq 2^u \cdot 5^w \cdot w \leq n~)

  Nói cách khác, nếu ta đặt:

  • ~R(x) = \{z \vert (z \in N) \land (1 \leq z \leq x)\}~ là tập các số tự nhiên từ ~1~ đến ~x~
  • ~W(u, v) = R(\lfloor \frac{n}{2^u \cdot 5^v} \rfloor)~

  thì số lượng cặp số trên tương đương với:

Để đơn giản hóa việc tính toán, ta có thể áp dụng nguyên tắc bao hàm - loại trừ. Cụ thể hơn, nếu ta đặt:

Khi này, ta có ~T(u, v) = N_1(u, v) - N_2(u, v) - N_5(u, v) + N_{10}(u, v)~ ~\Rightarrow~ Tổng các giá trị ~T(u, v)~ với mọi ~u~ và ~v~ sẽ chính là số lượng phân số là số thập phân hữu hạn.

• Bây giờ, yêu cầu còn lại cần phải được giải quyết là tính các giá trị ~N_x(u, v)~ một cách hiệu quả.
  • Ta không thể thực hiện bằng cách duyệt qua từng giá trị ~w~ vì ta có thể phải duyệt qua ~O(n)~ giá trị khác nhau.
  • Tuy nhiên, ta có nhận xét rằng chỉ có ~O(\sqrt n)~ giá trị ~\lfloor \frac{n}{w}\rfloor~ khác nhau.

Dựa vào nhận xét này, thay vì xem xét từng giá trị ~w~, ta xem xét gộp các giá trị ~w~ mà có cùng giá trị ~\lfloor \frac{n}{w} \rfloor~ vào cùng một nhóm. Cụ thể, ta sẽ có ~O(\sqrt n)~ nhóm gồm các giá trị liên tiếp nhau.

Ta thấy rằng tổng các giá trị ~\lfloor \frac{n}{w} \rfloor~ trong cùng một nhóm có thể được xác định dễ dàng với độ phức tạp thời gian ~O(1)~. Việc tính giá trị ~N_x(u, v)~ sẽ dựa vào việc ta thao tác trên các nhóm này.

Độ Phức Tạp

• Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(t \cdot (\sqrt n + \log^2 n))~:
  • Bước xác định nhóm có độ phức tạp ~O(\sqrt n)~ bởi ta có ~O(\sqrt n)~ nhóm.
  • Bước duyệt qua từng thành phần ~2^u \cdot 5^v~ nêu trên và đếm số lượng có độ phức tạp ~O(\log^2 n)~ nếu ta thực hiện offline (ta thực hiện duyệt và đếm cùng lúc với xác định từng nhóm theo thứ tự).
• Về bộ nhớ, ý tưởng nêu trên có thể được cài đặt với độ phức tạp ~O(\log^2 n)~ để lưu các thành phần ~2^u \cdot 5^v~ nêu trên.
• Lưu ý: Ý tưởng trên vẫn có thể được cài đặt theo nhiều cách khác với độ phức tạp khác với độ phức tạp nêu trên.

Code Minh Họa

#include <bits/stdc++.h>
using namespace std;

constexpr int FIXED_NUMBER_COUNT = 371;
constexpr long long MOD = 1E9 + 7, FIXED_NUMBERS[] = {1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 128, 160, 200, 250, 256, 320, 400, 500, 512, 625, 640, 800, 1000, 1024, 1250, 1280, 1600, 2000, 2048, 2500, 2560, 3125, 3200, 4000, 4096, 5000, 5120, 6250, 6400, 8000, 8192, 10000, 10240, 12500, 12800, 15625, 16000, 16384, 20000, 20480, 25000, 25600, 31250, 32000, 32768, 40000, 40960, 50000, 51200, 62500, 64000, 65536, 78125, 80000, 81920, 100000, 102400, 125000, 128000, 131072, 156250, 160000, 163840, 200000, 204800, 250000, 256000, 262144, 312500, 320000, 327680, 390625, 400000, 409600, 500000, 512000, 524288, 625000, 640000, 655360, 781250, 800000, 819200, 1000000, 1024000, 1048576, 1250000, 1280000, 1310720, 1562500, 1600000, 1638400, 1953125, 2000000, 2048000, 2097152, 2500000, 2560000, 2621440, 3125000, 3200000, 3276800, 3906250, 4000000, 4096000, 4194304, 5000000, 5120000, 5242880, 6250000, 6400000, 6553600, 7812500, 8000000, 8192000, 8388608, 9765625, 10000000, 10240000, 10485760, 12500000, 12800000, 13107200, 15625000, 16000000, 16384000, 16777216, 19531250, 20000000, 20480000, 20971520, 25000000, 25600000, 26214400, 31250000, 32000000, 32768000, 33554432, 39062500, 40000000, 40960000, 41943040, 48828125, 50000000, 51200000, 52428800, 62500000, 64000000, 65536000, 67108864, 78125000, 80000000, 81920000, 83886080, 97656250, 100000000, 102400000, 104857600, 125000000, 128000000, 131072000, 134217728, 156250000, 160000000, 163840000, 167772160, 195312500, 200000000, 204800000, 209715200, 244140625, 250000000, 256000000, 262144000, 268435456, 312500000, 320000000, 327680000, 335544320, 390625000, 400000000, 409600000, 419430400, 488281250, 500000000, 512000000, 524288000, 536870912, 625000000, 640000000, 655360000, 671088640, 781250000, 800000000, 819200000, 838860800, 976562500, 1000000000, 1024000000, 1048576000, 1073741824, 1220703125, 1250000000, 1280000000, 1310720000, 1342177280, 1562500000, 1600000000, 1638400000, 1677721600, 1953125000, 2000000000, 2048000000, 2097152000, 2147483648, 2441406250, 2500000000, 2560000000, 2621440000, 2684354560, 3125000000, 3200000000, 3276800000, 3355443200, 3906250000, 4000000000, 4096000000, 4194304000, 4294967296, 4882812500, 5000000000, 5120000000, 5242880000, 5368709120, 6103515625, 6250000000, 6400000000, 6553600000, 6710886400, 7812500000, 8000000000, 8192000000, 8388608000, 8589934592, 9765625000, 10000000000, 10240000000, 10485760000, 10737418240, 12207031250, 12500000000, 12800000000, 13107200000, 13421772800, 15625000000, 16000000000, 16384000000, 16777216000, 17179869184, 19531250000, 20000000000, 20480000000, 20971520000, 21474836480, 24414062500, 25000000000, 25600000000, 26214400000, 26843545600, 30517578125, 31250000000, 32000000000, 32768000000, 33554432000, 34359738368, 39062500000, 40000000000, 40960000000, 41943040000, 42949672960, 48828125000, 50000000000, 51200000000, 52428800000, 53687091200, 61035156250, 62500000000, 64000000000, 65536000000, 67108864000, 68719476736, 78125000000, 80000000000, 81920000000, 83886080000, 85899345920, 97656250000, 100000000000, 102400000000, 104857600000, 107374182400, 122070312500, 125000000000, 128000000000, 131072000000, 134217728000, 137438953472, 152587890625, 156250000000, 160000000000, 163840000000, 167772160000, 171798691840, 195312500000, 200000000000, 204800000000, 209715200000, 214748364800, 244140625000, 250000000000, 256000000000, 262144000000, 268435456000, 274877906944, 305175781250, 312500000000, 320000000000, 327680000000, 335544320000, 343597383680, 390625000000, 400000000000, 409600000000, 419430400000, 429496729600, 488281250000, 500000000000, 512000000000, 524288000000, 536870912000, 549755813888, 610351562500, 625000000000, 640000000000, 655360000000, 671088640000, 687194767360, 762939453125, 781250000000, 800000000000, 819200000000, 838860800000, 858993459200, 976562500000, 1000000000000};

long long findCeil(const long long x, const long long y) {
    return (x + y - 1) / y;
}

long long countMultiples(const long long l, const long long r, const long long d) {
    return max(r / d - findCeil(l, d) + 1, 0LL);
}

long long n, f, l, r, query, sum1, sum2, sum5, sum10, result, queries[FIXED_NUMBER_COUNT];
int t, q, i;

int findSum1() {
    return (sum1 + f * ((query - l + 1) % MOD)) % MOD;
};

int findSum2() {
    return (sum2 + f * (((query >> 1) - (l + 1 >> 1) + 1) % MOD)) % MOD;
};

int findSum5() {
    return (sum5 + f * (countMultiples(l, query, 5) % MOD)) % MOD;
};

int findSum10() {
    return (sum10 + f * (countMultiples(l, query, 10) % MOD)) % MOD;
};

int countFractions() {
    result = n % MOD;
    q = 0;
    sum1 = sum2 = sum5 = sum10 = 0;
    l = 1;

    (result *= result) %= MOD;

    for (i = 0; i < FIXED_NUMBER_COUNT && FIXED_NUMBERS[i] <= n; ++i)
        queries[q++] = n / FIXED_NUMBERS[i];

    reverse(queries, queries + q);

    for (i = 0; l <= n; l = r + 1) {
        f = n / l;
        r = n / f;
        for (f %= MOD; i < q && queries[i] <= r; ++i) {
            query = queries[i];
            if ((result += findSum2()) >= MOD)
                result -= MOD;
            if ((result += findSum5()) >= MOD)
                result -= MOD;
            if ((result -= findSum1()) < 0)
                result += MOD;
            if ((result -= findSum10()) < 0)
                result += MOD;
        }
        query = r;
        sum1 = findSum1();
        sum2 = findSum2();
        sum5 = findSum5();
        sum10 = findSum10();
    }

    return result;
}

signed main() {
    int t = 0;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> t;

    for (int i = 1; i <= t; ++i) {
        cin >> n;
        cout << countFractions() << '\n';
    }

    return 0;
}

Lời giải 2

Cho số nguyên dương ~n~, đếm số cặp (~a, b~) (~1 \le a, b \le n~) thoả mãn ~\frac{a}{b}~ là số thập phân vô hạn.

Subtask 1

~\frac{a}{b}~ là số thập phân vô hạn ~\Leftrightarrow~ mẫu số của ~\frac{a}{b}~ sau khi rút gọn tồn tại ít nhất một thừa số nguyên tố khác ~2~ và ~5~. Chứng minh:

• Để đơn giản ta xét các phân số ~\frac{a}{b}~ là phân số tối giản, nghĩa là ~\text{gcd}(a,b)=1~.
• Chiều thuận: Giả sử ~\frac{a}{b}~ có biểu diễn thập phân hữu hạn. Khi đó tồn tại số nguyên không âm ~k~ sao cho ~10^k \cdot \frac{a}{b}~ là số nguyên, nghĩa là ~10^k~ chia hết cho ~b~ (do ~(a,b)=1~). Từ đó suy ra ~b~ chỉ chứa các ước nguyên tố ~2~ và ~5~.
• Chiều ngược: Giả sử ~b=2^x 5^y~, chọn ~k = \max(x,y)~, khi đó ta có ~10^k \cdot \frac{a}{b}~ là số nguyên ~\Rightarrow~ ~\frac{a}{b}~ là số thập phân hữu hạn.

Từ đó với mỗi test, ta có thể duyệt toàn bộ cặp ~(a, b)~ với ~1 \le a, b \le n~, và kiểm tra điều kiện bằng cách:

• Rút gọn phân số ~\frac{a}{b}~ bằng cách gán ~a \leftarrow \frac{a}{\text{gcd}(a, b)}~, ~b \leftarrow \frac{b}{\text{gcd}(a, b)}~
• Trong khi ~b~ còn chia hết cho ~2~, chia ~b~ cho ~2~. Tương tự với ~5~.
• Nếu ~b>1~ tức là ~b~ còn chứa một thừa số nguyên tố khác ~2~ và ~5~, ta tăng đáp án lên ~1~.

Độ phức tạp của việc duyệt là ~\mathcal{O}(n^2 \log n)~, tuy nhiên không phải việc tính ~\text{gcd}~ lúc nào cũng mất ~\log n~ nên có thể vẫn qua được hết test. Tuy nhiên ta có thể tính trước các mảng:

• ~g(i, j)~ là ước chung lớn nhất của hai số ~i~ và ~j~,
• ~f(i)~ trả về ~\texttt{true}~ nếu ~i~ chỉ chứa thừa số nguyên tố ~2~ và ~5~, ~\texttt{false}~ nếu ngược lại.

để việc kiểm tra với mỗi test chỉ còn ~\mathcal{O}(n^2)~, đưa độ phức tạp về ~\mathcal{O}(tn^2)~

Cài đặt mẫu:

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int g[N][N];
bool f[N];

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

  for (int i = 1; i < N; i++) {
    g[i][i] = i;
    for (int j = i + 1; j < N; j++) {
      g[i][j] = g[j][i] = __gcd(i, j);
    }
  }

  for (int i = 1; i < N; i++) {
    int x = i;
    while (x % 2 == 0) x /= 2;
    while (x % 5 == 0) x /= 5;
    f[i] = x == 1;
  }

  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (!f[j / g[i][j]]) {
          cnt++;
        }
      }
    }
    cout << cnt << '\n';
  }

  return 0;
}

Subtask 2

Thay vì đếm số lượng số thập phân vô hạn, ta có thể đếm phần bù bằng cách tính số lượng số thập phân hữu hạn, sau đó lấy ~n^2~ trừ đi là ra đáp án cần tìm.

Nhận thấy việc rút gọn phân số như ở subtask 1 là quá tổng quát và không cần thiết cho việc đếm, mà ta chỉ cần biểu diễn phân số ~\frac{a}{b}~ dưới dạng:

với:

• ~c~ không chứa thừa số nguyên tố ~2~ và ~5~,
• ~b'~ chỉ chứa thừa số nguyên tố ~2~ và ~5~,
• ~a'~ bất kì.

là đủ, vì ta chỉ cần biết mẫu số sau khi rút gọn chỉ còn các thừa số ~2~ và ~5~ hay không.

Từ đó thay vì duyệt ~a~ và ~b~, ta sẽ duyệt ~c~ và đếm số cặp (~a',b'~) có dạng như trên. Với mỗi ~c~:

• Số lượng ~a'~ thoả mãn là ~\lfloor \frac{n}{c} \rfloor~
• Số lượng ~b'~ thoả mãn là: số lượng số có dạng ~2^i \times 5^j~ và có giá trị ~\le \lfloor \frac{n}{c} \rfloor~
  • Ta có thể chuẩn bị trước các số có dạng ~2^i \times 5^j~ theo thứ tự tăng dần vào một mảng. Từ đó với mỗi ~c~, ta có thể dùng hai con trỏ để đếm số lượng số ~b'~ thoả mãn do ~c~ tăng dần ~\Rightarrow~ ~\lfloor \frac{n}{c} \rfloor~ giảm dần.
• Từ đó ta cộng vào đáp án một lượng: (Số lượng ~a'~ thoả mãn) ~\times~ (Số lượng ~b'~ thoả mãn).

Đáp án không vượt quá ~10^{12}~, nên ta có thể dùng kiểu ~\texttt{int64}~ và tiến hành mod sau khi đã tính toán xong.

Độ phức tạp: ~\mathcal{O}(tn)~

Cài đặt mẫu:

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

bool f[N];
vector<int> cand;

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

  for (int i = 1; i < N; i++) {
    int x = i;
    while (x % 2 == 0) x /= 2;
    while (x % 5 == 0) x /= 5;
    f[i] = x == 1;
    if (f[i]) {
      cand.emplace_back(i);
    }
  }

  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    int64_t ans = 0;
    int ptr = int(cand.size()) - 1;
    for (int c = 1; c <= n; c++) {
      if (c % 2 == 0 || c % 5 == 0) {
        continue;
      }
      // x <= n/c
      // y <= n/c and f[y] == 1
      while (ptr >= 0 && 1ll * cand[ptr] * c > n) --ptr;
      ans += 1ll * (n / c) * (ptr + 1);
    }
    cout << (1ll * n * n - ans) % mod << '\n';
  }

  return 0;
}

Subtask 3

Nhận xét:

• Chỉ có tối đa ~2\sqrt{n}~ giá trị ~\lfloor \frac{n}{c} \rfloor~ phân biệt.
  • Nếu ~c \le \sqrt{n}~, rõ ràng số lượng giá trị phân biệt tương ứng với số lượng số ~c~, là ~\sqrt{n}~
  • Nếu ~c > \sqrt{n}~, thì ~\lfloor \frac{n}{c} \rfloor~ chỉ nhận các giá trị nguyên từ ~1~ đến ~\sqrt{n}~.
  • Tổng lại ta có số lượng giá trị phân biệt tối đa là ~2\sqrt{n}~.
• Các giá trị ~c~ có cùng kết quả khi tính ~\lfloor \frac{n}{c} \rfloor~ nằm trên một đoạn liên tiếp của trục số.
  • Điều này là dễ thấy dựa vào tính chất đơn điệu của dãy ~\lfloor \frac{n}{c} \rfloor~ như đã trình bày ở subtask 2.
• Nếu cố định ~\lfloor \frac{n}{c} \rfloor~, thì đáp án là giống nhau cho dù ~c~ có thay đổi.

Như vậy ta chỉ cần thay đổi phần duyệt ở subtask 2:

• Ta sẽ duyệt qua các đoạn ~[l,r]~ sao cho ~\lfloor \frac{n}{c} \rfloor~ là cố định với mọi ~c~ thuộc đoạn ~[l,r]~.
• Với mỗi đoạn ~[l,r]~ như vậy, cộng vào đáp án một lượng ~\text{số lượng số trong đoạn [l, r] không chia hết cho 2 hoặc 5}~ ~\times~ ~\lfloor \frac{n}{l} \rfloor~ ~\times~ ~\text{số lượng giá trị b' thoả mãn}~
  • Sử dụng bao hàm loại trừ để tính số lượng số trong đoạn ~[l, r]~ không chia hết cho ~2~ hoặc ~5~.
  • Cách tính số lượng giá trị ~b'~ thoả mãn giống như ở subtask 2. Tuy nhiên việc chuẩn bị cần phải tinh tế hơn: thay vì duyệt từ ~1~ đến ~n~ rồi kiểm tra, ta chỉ duyệt các cặp ~(i, j)~ và tính giá trị ~2^i \times 5^j~. Nhận thấy ~i, j \le \log_2 (n)~ nên ta có thể duyệt trâu và sắp xếp được.

Vấn đề cuối cùng là duy trì tập các đoạn ~[l,r]~:

• Ta có thể duyệt ~l~ tăng dần từ ~1~. Với mỗi ~l~, ta chặt nhị phân tìm ~r~ xa nhất sao cho ~\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{r} \rfloor~. Sau khi tính toán xong, gán ~l \leftarrow r+1~.
• Tuy nhiên độ phức tạp cho việc trên có thể lên đến ~\mathcal{O}(t \sqrt{n} \log {n})~.
• Ta có thể tìm ~r~ trong ~\mathcal{O}(1)~. Đặt ~q = \lfloor \frac{n}{l} \rfloor~, thì ~r = \lfloor \frac{n}{q} \rfloor~.
  • Do nếu ta có ~i~ thoả mãn ~\lfloor \frac{n}{i} \rfloor = q~, thì ~i \le \frac{n}{q}~, từ đó ta chọn được số lớn nhất mà vẫn thoả mãn điều kiện.

Độ phức tạp: ~\mathcal{O}(t \sqrt{n})~

Cài đặt mẫu:

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

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

  vector<int64_t> cand;
  for (int64_t i = 1; i <= 1e12; i *= 2) {
    for (int64_t j = 1; j <= 1e12 / i; j *= 5) {
      cand.emplace_back(i * j);
    }
  }
  sort(cand.begin(), cand.end());

  int tc;
  cin >> tc;
  while (tc--) {
    int64_t n;
    cin >> n;
    __int128_t ans = 0;
    int ptr = int(cand.size()) - 1;
    auto f = [&](int64_t l, int64_t r, int64_t d) {
      return (r / d - (l - 1) / d);
    };
    auto count_numerator = [&](int64_t l, int64_t r) {
      return f(l, r, 1) - f(l, r, 2) - f(l, r, 5) + f(l, r, 10);
    };
    for (int64_t lc = 1; lc <= n;) {
      int64_t nc = n / lc;
      int64_t rc = n / nc;

      while (ptr >= 0 && cand[ptr] > nc) --ptr;
      // so so trong doan [lc, rc] khong chia het cho 2 va 5
      ans += __int128_t(count_numerator(lc, rc)) * nc * (ptr + 1);

      lc = rc + 1;
    }
    cout << (int)((__int128_t(n) * n - ans) % MOD) << '\n';
  }

  return 0;
}