Đếm Cặp

Xem PDF

Đ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;
    }
    

    • -3
      Bao29102010    4:23 p.m. 25 Tháng 7, 2024

      Code C++ nhé mng:

      #include <bits/stdc++.h>
      #include <math.h>
      int tinh(int n)
      {
      return sqrt(n)*2+1;
      }
      using namespace std;
      int main()
      {
      ios_base::sync_with_stdio(false);
      cin.tie(0); cout.tie(0);
      int t, n;
      cin>>t;
      while(t--)
      {
      cin>>n;
      cout<<tinh(n)<<endl;
      }
      }


      • 0
        Avocadorable    5:37 p.m. 26 Tháng 4, 2024
        from math import floor, sqrt
        
        t = int(input())
        
        for i in range(t):
            n = int(input())
            print(floor(sqrt(n)) * 2 + 1)
        

        • 0
          NTT_36    12:30 a.m. 20 Tháng 10, 2023 chỉnh sửa 17

          Ai cần gợi ý không

          1 phản hồi

          • 0
            lehuy_1704209    8:42 a.m. 27 Tháng 8, 2023

            include <bits/stdc++.h>

            using namespace std;
            long long n,a;
            int sc (long long n)
            {
            int r=sqrt(n);
            return r*2+1;
            }
            int main()
            {
            ios::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            cin>>a;
            for(int i=1;i<=a;i++)
            {
            cin>>n;
            cout<<sc(n)<<" ";
            }
            }


            • 0
              xthabao1    11:09 p.m. 10 Tháng 8, 2023

              khó quá SOS
              haizzzz
              uhmmmm


              • 0
                phambinminh12345    2:32 p.m. 14 Tháng 11, 2021

                hello mn :)))


                • 0
                  tienduyyl    2:32 p.m. 14 Tháng 11, 2021

                  hello mn 🙂


                  • 2
                    todonghai2k7    8:16 p.m. 19 Tháng 8, 2020

                    AC bài này đã rồi mới AC bài trên :))))


                    • 2
                      N7hoatt    8:09 p.m. 19 Tháng 8, 2020

                      gợi ý các TH:x=0, x<0, x>0

                      1 phản hồi
                      • 1 bình luận nữa