Đếm Cặp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
TCA_Khoa
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một số nguyên dương \(N\).

Yêu cầu:

  • Đếm số cặp số nguyên \((x, y)\) thỏa mãn:
  • \(x^2 + y = N\)
  • \(y ≥ 0\)

Input

  • Dòng đầu tiên chứa một số nguyên dương T (T \(\leq 10^5\) ), là số lượng truy vấn.
  • T dòng tiếp theo mỗi dòng chứa số nguyên dương \(N\) (\(N \leq 10^{9})\).

Output

  • In ra T dòng mỗi dòng là kết quả cần tìm.

Example

Test 1

Input 
2
2
9
Output 
3
7
Note

với \(N = 2\) thì sẽ có các cặp \((1, 1); (0, 2); (-1, 1)\)

với \(N = 9\) thì sẽ có các cặp \((-2, 5); (0, 9); (-3, 0); (-1, 8); (2, 5); (1, 8); (3, 0)\)

Bình luận


  • 2
    lehongduc    10:40 p.m. 20 Tháng 8, 2024
    hint

    ta nhận thấy với mọi giá trị từ 0 đến sqrt(n) luôn có giá trị x,y thỏa mãn
    và mỗi giá trị x,y thỏa mãn sẽ luôn có giá trị -x,y thỏa mãn nhưng 0 là trường hợp đặt biệt (vì 0 = -0)
    nên ta có công thức
    số cặp x,y thỏa mãn là 1+sqrt(n)*2 (nhớ ép kiểu sang integer
    độ phức tạp O(1)

    code C++ 
    #include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    while(t>0)
    {
        t--;
        ll n;
        cin>>n;
        cout<<1+(ll)sqrt(abs(n))*2<<endl;
    }
    return 0;
}
      • 10 bình luận nữa