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

Question

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 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
Замечание
Подзадачи:

10 баллов: k 6 10
15 баллов: k 6 1 000
20 баллов: k 6 105
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};

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

Answer 1

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

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

$k \le 10$ — 10 баллов
$k \le 1000$ — 15 баллов
$k \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

Это простое число больше $10^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)

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

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

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

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

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

Answer 2

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

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

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

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

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

text
k = 999999937

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

x=p^2\approx10^{18}

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

x\mathrel{*}=p,

то есть пытаешься получить примерно $10^{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\le10^9$ достаточно простых до $\sqrt{10^9}\approx31623$ , а у тебя решето до $10^5$ .

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

ab=k(a+b)

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

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

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

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

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

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

Domanda

Pensiero

Risposta

Domanda

Pensiero

Risposta

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

Condividi questa Q&A