Đ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
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++
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;
}
}
Ai cần gợi ý không
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)<<" ";
}
}
khó quá SOS
haizzzz
uhmmmm
hello mn :)))
hello mn 🙂
AC bài này đã rồi mới AC bài trên :))))
gợi ý các TH:x=0, x<0, x>0
1 bình luận nữa