Dãy các số vuông tam giác

View as PDF
Submit solution
Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
admin
Suggester:
admin
Problem type

Một số tự nhiên được gọi là số STN nếu thỏa mãn hai điều kiện:

  • Số chính phương là số có thể viết dưới dạng ~n^2~ (ví dụ: 1, 4, 9, 16, 25, 36, …).;
  • Số tam giác là số có thể viết dưới dạng: ~T_n = \frac{n(n+1)}{2}~ .

Sắp xếp tăng dần các số STN ta được dãy vô hạn số STN, các số đầu tiên của dãy là: 1, 36, 1225, 41616, 1413721, 48024900,…

Yêu cầu: Cho hai số nguyên dương 𝑘 và 𝑀, gọi 𝑁 là số STN thứ 𝑘 trên dãy (các số trên dãy được đánh thứ tự bắt đầu từ 1), tính phần dư khi chia 𝑁 cho 𝑀.

Dữ liệu vào: là dạng chuẩn có định dạng như sau:

  • Dòng đầu ghi số nguyên dương 𝑇 (𝑇 ≤ 100) là số bộ dữ liệu;
  • 𝑇 dòng sau, mỗi dòng tương ứng với một bộ dữ liệu chứa hai số nguyên dương 𝑘, 𝑀.

Dữ liệu ra: gồm 𝑇 dòng tương ứng với 𝑇 bộ dữ liệu trong dữ liệu vào, mỗi dòng ghi một số là phần dư khi chia 𝑁 cho 𝑀.

Ví dụ

Input:

2
2 10
5 10

Output:

6
1

Ràng buộc:

  • Có 20% số test có ~𝑘 ≤ 5; 𝑀 ≤ 10^9~;
  • Có 20% số test khác có ~𝑘 ≤ 10; 𝑀 ≤ 10^9;
  • Có 20% số test khác có ~𝑘 ≤ 20; 𝑀 ≤ 10^9;
  • Có 20% số test khác có ~𝑘 ≤ 10^9; 𝑀 ≤ 10^9~;
  • Có 20% số test còn lại có ~𝑘 ≤ 10^18; 𝑀 ≤ 10^18~.

Comments

Please read the guidelines before commenting.


  • 0
    tcu_01   commented on Sept. 13, 2025, 9:01 p.m.

    include <bits/stdc++.h>

    using namespace std; using ll = long long; using u128 = _uint128t; // để in ra dễ hơn khi cần kiểm tra

    // Nhân nhanh kiểu Ấn Độ: (a * b) % mod, tránh tràn 64-bit ll mulmod(ll a, ll b, ll mod) { _int128 res = 0; __int128 x = a % mod, y = b; while (y > 0) { if (y & 1) res = (res + x) % mod; x = (x + x) % mod; y >>= 1; } return (ll)res; }

    // Nhân 2 ma trận 2x2 mod M void matmul(ll A[2][2], ll B[2][2], ll M, ll C[2][2]) { ll res[2][2]; res[0][0] = ( (mulmod(A[0][0], B[0][0], M) + mulmod(A[0][1], B[1][0], M)) % M ); res[0][1] = ( (mulmod(A[0][0], B[0][1], M) + mulmod(A[0][1], B[1][1], M)) % M ); res[1][0] = ( (mulmod(A[1][0], B[0][0], M) + mulmod(A[1][1], B[1][0], M)) % M ); res[1][1] = ( (mulmod(A[1][0], B[0][1], M) + mul_mod(A[1][1], B[1][1], M)) % M ); C[0][0] = res[0][0]; C[0][1] = res[0][1]; C[1][0] = res[1][0]; C[1][1] = res[1][1]; }

    // Lũy thừa ma trận nhanh void mat_pow(ll base[2][2], long long exp, ll M, ll res[2][2]) { // ma trận đơn vị res[0][0] = 1 % M; res[0][1] = 0; res[1][0] = 0; res[1][1] = 1 % M;

    ll tmp[2][2];
while (exp > 0) {
    if (exp & 1) {
        mat_mul(res, base, M, tmp);
        memcpy(res, tmp, sizeof(tmp));
    }
    mat_mul(base, base, M, tmp);
    memcpy(base, tmp, sizeof(tmp));
    exp >>= 1;
}

    }

    // Tính yk theo công thức truy hồi y{n+1} = 6 yn - y{n-1} // y1 = 1, y2 = 6 ll yk_mod(long long k, ll M) { if (M == 1) return 0; if (k == 1) return 1 % M; if (k == 2) return 6 % M;

    ll T[2][2] = { {6 % M, (M-1) % M}, {1 % M, 0} }; // [[6, -1], [1, 0]]
ll P[2][2];
mat_pow(T, k - 2, M, P);

ll y2 = 6 % M, y1 = 1 % M;
ll yk = (mul_mod(P[0][0], y2, M) + mul_mod(P[0][1], y1, M)) % M;
return yk;

    }

    // Trả về (yk^2) % M ll squaretriangularmod(long long k, ll M) { ll y = ykmod(k, M); return mul_mod(y, y, M); }

    int main() { ios::syncwithstdio(false); cin.tie(nullptr); freopen("input.05","r",stdin);
    freopen("output.05","w",stdout); int T; cin >> T; while (T--) { long long k, M; cin >> k >> M; cout << squaretriangularmod(k, M) << "\n"; } return 0; }