Hướng dẫn giải của Cặp số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Điều kiện ~xy + x + y = N~ tương đương với ~(x+1)(y+1) = N+1~. Vậy đáp án là số ước của ~N+1~ trừ đi 2 (bỏ ước 1 và ~N+1~ vì x, y phải dương).
Sub 1: Thử từng x — ~O(N)~, dùng khi ~N \le 10^6~
Với mỗi x từ 1 đến N-1, nếu ~(x+1)\mid (N-x)~ thì y = (N-x)/(x+1); đếm khi y \ge 1.
Nếu chỉ nộp sub này: đúng 10/12 test.
Sub 2: Phân tích thừa số — ~O(\sqrt{N})~
Phân tích ~N+1~ thành thừa số nguyên tố; số ước là tích của (số mũ + 1). Đáp án là số ước trừ 2.
Nếu chỉ nộp sub này: đúng 12/12 test.
Chương trình hoàn chỉnh
Chương trình đọc N. Nếu N \le 10^6 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Dieu kien: x*y + (x+y) = N <=> (x+1)(y+1) = N+1.
// Sub 1: thu tung x, kiem tra y = (N-x)/(x+1) nguyen va >= 1. O(N). Dung khi N <= 10^6
long long sub1() {
long long cnt = 0;
for (long long x = 1; x < N; x++) {
if ((N - x) % (x + 1) == 0) {
long long y = (N - x) / (x + 1);
if (y >= 1) cnt++;
}
}
return cnt;
}
// Sub 2: dem uoc cua N+1 bang phan tich thua so, roi bo 2 truong hop x=0 hoac y=0 (uoc 1 va N+1). O(sqrt N)
long long sub2() {
long long m = N + 1;
long long cnt = 1;
for (long long p = 2; p * p <= m; p++) {
int e = 0;
while (m % p == 0) {
m /= p;
e++;
}
cnt *= (e + 1);
}
if (m > 1) cnt *= 2;
return cnt - 2;
}
int main() {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
cin >> N;
if (N <= 1000000) cout << sub1() << "\n";
else cout << sub2() << "\n";
return 0;
}
Bình luận