Cho mình hỏi cách xử lý những bài có test lớn

MACHINE 2021-11-09 9:41:42

Mình đang làm các bài như Handshake - Bắt Tay; Sum - Tính Tổng; Cutting - Cắt Bánh Sinh Nhật, và mình đều không AC được các test lớn. Mọi người cho mình hỏi là với những bài như này mình phải dùng Xử Lý Số Lớn hay là có cách nào khác ạ, mọi người hướng dẫn giúp mình. Mình xin cảm ơn!

Tổng cộng 2 trả lời

MACHINE

@Chùm CUỐI Dạ vâng em cảm ơn ạ!

Trùm CUỐI

Do tính toán bị tràn số bạn nhé.

#include <bits/stdc++.h>
using namespace std;
int N;
int main() {
    cin >> N;
    cout << (N - 1) * N / 2;
}

Ví dụ bài Handshake này, do n có thể tới 10^6 nên biểu thức \frac{n\times (n-1)}{2} có thể đạt tới 5\times 10^{11} nên sẽ vượt quá khả năng biểu diễn của số nguyên 32 bit , bạn cần tính toán với số 64 bit là được. Ví dụ:

#include <bits/stdc++.h>
using namespace std;
int N;
int main() {
    cin >> N;
    cout << 1ll * (N - 1) * N / 2; //Ép kiểu sang tính toán với kiểu 64 bit (long long)
}