UOCLE - Tìm ước số lẻ lớn nhất của số N
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho số nguyên dương ~n~. Tìm ước số lẻ lớn nhất của ~n~ nhỏ hơn ~n~.
Input
- Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
- ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~.
Giới hạn:
- ~1 ≤ T ≤ 10^5, 2 ≤ n ≤ 10^6~.
Output
- Với mỗi số nguyên dương ~n~, ghi ra trên một dòng ước số lẻ lớn nhất của ~n~ nhỏ hơn ~n~.
Sample
Input #1
3
3
8
15
Output #1
1
1
5
Problem source: Chuyên Sơn La Online Judge
Bình luận
dễ nhận thấy ước lớn nhất của n là n/x
x là ước nhỏ nhất của n
mà ta cần n/x là số lẻ nên ta sẽ có 2 trường hợp
TH 1 x=2
thì thì ước lẻ lớn nhất của n là n/(2^p) bài toán sẽ trở thành tìm p lớn nhất
TH 2 x!=2
đáp án là n/f[x];
với f[x] là số nguyên tố nhỏ nhất của x khi phân tích thừa số nguyên tố
include <iostream>
include <cmath>
using namespace std; int main() { int t; cin >> t; while(t--) { long long n; cin >> n; long long ans = 1; for(long long i = 1; i*i <= n; i++) { if(n % i == 0) { long long d1 = i; long long d2 = n / i; // chỉ xét ước lẻ nhỏ hơn n if(d1 % 2 == 1 && d1 < n) ans = max(ans, d1); if(d2 % 2 == 1 && d2 < n) ans = max(ans, d2); } } cout << ans << endl; } }
testcase 2 la j vay moi nguoi
test 2 là không có ước nào vẫn in ra 1 bạn ạ
phan tich thua so nguyen to nha
sao test 3 không AC được
tại sao lại bị timelimit của test 3 vậy ạ