logoChat01.ai

Имя входного файла: стандартный ввод Имя выходного...

생성일: 2026년 9월 17일

답변에 사용된 모델 GPT-5.6 by Chat01

질문

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Собрав волю в кулак, неудачники решили дать отпор Пеннивайзу и ворваться в его страшный
дом. Но трудности возникли уже на входе. Дело в том, что чтобы пройти в дом, нужно решить
следующую задачу:
Для заданного числа k найдите и выведите все пары натуральных чисел (a, b) такие, что a · b
ровно в k раз больше чем a + b.
Помогите неудачникам и выведите все подходящие пары в лексикографическом порядке.
Формат входных данных
Первая строка ввода содержит единственное целое число k (1 6 k 6 109).
Формат выходных данных
В первой строке выведите единственное целое число n — число различных пар.
Далее в n строках в лексикографическом порядке выведите эти пары. Каждая пара должна
встречаться ровно один раз. Пары, отличающиеся порядком своих элементов, считаются различными.
Примеры
стандартный ввод стандартный вывод
11 3
12 132
22 22
132 12
12 15
13 156
14 84
15 60
16 48
18 36
20 30
21 28
24 24
28 21
30 20
36 18
48 16
60 15
84 14
156 13
Замечание
Подзадачи:

  1. 10 баллов: k 6 10
  2. 15 баллов: k 6 1 000
  3. 20 баллов: k 6 105
  4. 55 баллов: полные ограничения

#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

void solve() {
int k;
cin >> k;

vector< bool > b(N);
vector< int > pr;
for (int i = 2; i < N; i++) {
if (!b[i]) {
pr.push_back(i);

text
  int j = i + i;
  while (j < N) {
    b[j] = 1;
    j += i;
  }
}

}

int d = k;
vector< int > vos(pr.size(), 0);
for (int i = 0; i < pr.size(); i++) {
while (d % pr[i] == 0) {
vos[i]++;
d /= pr[i];
}
vos[i] *= 2;
}
if (d != 1) {
pr.push_back(d);
vos.push_back(2);
}

set< pair< int, int > > ans;
function< void(int, int) > f = [&](int x, int i) {
if (i + 1 >= vos.size()) {
int b = x + k;
int a = (k * k) / (b - k) + k;
return;
}
while (vos[i + 1] == 0) {
i++;
if (i + 1 >= vos.size()) {
int b = x + k;
int a = (k * k) / (b - k) + k;
ans.insert({a, b});
return;
}
}

text
int cnt = vos[i + 1] + 1;
while (cnt--) {
  f(x, i + 1);
  x *= pr[i + 1];
}

};
f(1, -1);

cout << ans.size() << "\n";
for (auto [a, b] : ans) {
cout << a << " " << b << "\n";
}
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}

return 0;
}
/*
int d[2][2][700] = {i, j, x};

*/
это сколько баллов?

사고

Estimating subtask performance

I’m finding that the divisor enumeration works when every prime factor is handled, including small constraints. However, leftover large prime factors cause recursion to omit solutions, so full-score tests likely fail while early subtasks may pass.

Estimated subtask performance

Worked for 18s

답변

Скорее всего 45 баллов из 100.

Первые три подзадачи твой код должен проходить:

  • k≤10k \le 10 — 10 баллов
  • k≤1000k \le 1000 — 15 баллов
  • k≤105k \le 10^5 — 20 баллов

Итого 45.

Проблема вот здесь:

cpp
if (i + 1 >= vos.size()) {
  int b = x + k;
  int a = (k * k) / (b - k) + k;
  return;
}

Ты вычисляешь a и b, но не добавляешь их в ans.

Это проявляется, когда после факторизации остаётся простой множитель d, который ты дописываешь сюда:

cpp
if (d != 1) {
  pr.push_back(d);
  vos.push_back(2);
}

Например, возьмём

text
k = 1000003

Это простое число больше 10510^5. Оно не содержится в твоём решете, поэтому попадёт в d, затем будет добавлено последним элементом pr.

Рекурсия в итоге вызовет f(..., i), где i — последний индекс, попадёт сюда:

cpp
if (i + 1 >= vos.size()) {
    ...
    return;
}

и ничего не добавит.

То есть для такого k программа фактически выведет:

text
0

хотя должно быть 3 пары.

Исправление элементарное:

cpp
if (i + 1 >= vos.size()) {
  int b = x + k;
  int a = (k * k) / (b - k) + k;
  ans.insert({a, b});
  return;
}

После этого, насколько я вижу, решение уже должно претендовать на 100 баллов. Формула у тебя верная, потому что

ab=k(a+b)ab=k(a+b)

эквивалентно

(a−k)(b−k)=k2.(a-k)(b-k)=k^2.

Поэтому достаточно перебрать все делители x∣k2x\mid k^2 и получить

b=k+x,a=k+k2x.b=k+x,\qquad a=k+\frac{k^2}{x}.

long long тоже хватает: при k≤109k\le10^9, k2≤1018k^2\le10^{18}.

질문

#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

void solve() {
int k;
cin >> k;

vector< bool > b(N);
vector< int > pr;
for (int i = 2; i < N; i++) {
if (!b[i]) {
pr.push_back(i);

text
  int j = i + i;
  while (j < N) {
    b[j] = 1;
    j += i;
  }
}

}

int d = k;
vector< int > vos(pr.size(), 0);
for (int i = 0; i < pr.size(); i++) {
while (d % pr[i] == 0) {
vos[i]++;
d /= pr[i];
}
vos[i] *= 2;
}
if (d != 1) {
pr.push_back(d);
vos.push_back(2);
}

set< pair< int, int > > ans;
function< void(int, int) > f = [&](int x, int i) {
if (i + 1 >= vos.size()) {
int b = x + k;
int a = (k * k) / (b - k) + k;
ans.insert({a, b});
return;
}
while (vos[i + 1] == 0) {
i++;
if (i + 1 >= vos.size()) {
int b = x + k;
int a = (k * k) / (b - k) + k;
ans.insert({a, b});
return;
}
}

text
int cnt = vos[i + 1] + 1;
while (cnt--) {
  f(x, i + 1);
  x *= pr[i + 1];
}

};
f(1, -1);

cout << ans.size() << "\n";
for (auto [a, b] : ans) {
cout << a << " " << b << "\n";
}
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}

return 0;
}
/*
int d[2][2][700] = {i, j, x};

*/

а этот

사고

Checking factorization logic

I’m reviewing divisor generation for indexing and overflow issues. The prime bound appears sufficient, but multiplying once beyond the final exponent could exceed the integer range, especially when constructing values near k2k^2.

Checked factorization logic

Worked for 8s

답변

Этот уже почти правильный, но я бы не гарантировал 100 баллов из-за переполнения в рекурсии.

Проблема здесь:

cpp
int cnt = vos[i + 1] + 1;
while (cnt--) {
  f(x, i + 1);
  x *= pr[i + 1];
}

После последнего вызова f ты всё равно ещё раз умножаешь x, хотя это значение больше не понадобится.

Например, если

text
k = 999999937

— большое простое число, то для него перебираются степени p0,p1,p2p^0,p^1,p^2. После вызова с

x=p2≈1018x=p^2\approx10^{18}

ты делаешь ещё:

x∗=p,x\mathrel{*}=p,

то есть пытаешься получить примерно 102710^{27}, что далеко за пределами long long. Это signed integer overflow → undefined behavior.

Исправь цикл, например так:

cpp
int cnt = vos[i + 1] + 1;
while (cnt--) {
  f(x, i + 1);
  if (cnt)
    x *= pr[i + 1];
}

или гораздо чище:

cpp
int pw = 1;
for (int j = 0; j <= vos[i + 1]; j++) {
  f(x * pw, i + 1);
  if (j != vos[i + 1])
    pw *= pr[i + 1];
}

Хотя во втором варианте надо также следить, чтобы x * pw <= k²; здесь это выполняется для настоящих делителей.

По остальному

Факторизация достаточная: при k≤109k\le10^9 достаточно простых до 109≈31623\sqrt{10^9}\approx31623, а у тебя решето до 10510^5.

Формула правильная:

ab=k(a+b)ab=k(a+b) (a−k)(b−k)=k2.(a-k)(b-k)=k^2.

Каждому делителю x∣k2x\mid k^2 соответствует

b=k+x,a=k+k2x.b=k+x,\qquad a=k+\frac{k^2}{x}.

set<pair<int,int>> автоматически выдаёт пары в требуемом лексикографическом порядке.

После исправления лишнего умножения я бы ожидал 100 баллов. В текущем виде на большинстве тестов код сработает, но из-за UB на больших простых формально полный балл не гарантирован.

이 Q&A 공유하기