Задача.Интересные числа.Помогите решить задачку.

Блог пользователя dnazirzhanov05

Автор dnazirzhanov05, история, 4 года назад, По-русски

ИНТЕРЕСНЫЕ ЧИСЛА. Назовём натуральное число X (X > 9) "интересным", если цифры в его десятичной записи ненулевые, попарно взаимно простые и их попарные суммы — простые числа. Например, число 114 является интересным, а числа 115, 124 — нет.
Найдите N-ое (1 <= N <= 2018) интересное число. Пример: 3 -> 14

dnazirzhanov05
4 года назад
9

Комментарии (9)

Написать комментарий?

veschii_nevstrui

4 года назад, # |

Напишем простой перебор, который покажет все интересные числа до $$$10^7$$$. Заметим, что все интересные числа либо двузначные, либо удовлетворяют регулярному выражению 1*[1246]1*. Скорее всего, это можно строго доказать, но мне лень(

Руками выкинем все двузначные. Из общего вида интересных чисел следует, что количество интересных чисел длины $$$n$$$ Равно $$$3 \cdot n + 1$$$. Из этой информации вы можете получить длину числа. В вашем случае сработает простой линейный перебор, однако для больших ограничений можно было бы использовать бинпоиск, или даже придумать явную формулу.

Затем осталось понять, какое именно у вас число, если известна его длина. Вы можете его явно перебрать, однако опять же, при больших ограничениях работал бы бинпоиск или явная формула.

Асимптотика решения: $$$O(n)$$$ если все просто перебирать, $$$O(\log{n})$$$, если придумать бинпоиск и $$$O(1)$$$, если придумать формулу.

→ Ответить

veschii_nevstrui

4 года назад, # ^ |

Строгое доказательство такое. Пусть есть интересное число, в котором больше одной не единичной цифры. Заметим, что если выкидывать цифры из числа, то это на интересность никак не влияет — она не может исчезнуть, только появиться. Будем выкидывать единицы либо пока они есть, либо пока число не станет трехзначным. Если кончились единицы, то будем выкидывать что угодно, пока число не останется трехзначным. Итого мы получили трехзначное интересное число, в котором хотя бы две не единичные цифры, а наш перебор показал, что таких чисел нет, противоречие.

Аналогичное рассуждение работает, если предположить, что в числе оказалась цифра не из множества $$$[1246]$$$.

→ Ответить

dnazirzhanov05

4 года назад, # ^ |

← Rev. 2 →

-8

Спасибо большое за вашу помощь.

→ Ответить

veschii_nevstrui

4 года назад, # ^ |

Я то могу, но какой в этом смысл? Для меня обучающей ценности эта задача не несет — я уже легко умею реализовывать подобное. Если я дам вам свой код, то вы, скорее всего, просто его сдадите в систему, возможно предварительно прочитав, но ничего не запомнив из этого полотна кода.

Гораздо лучше будет, если вы сами его напишете. Во-первых, я не потрачу свое бесценное время на простую задачу, а во-вторых, вы научитесь ее решать. Поверьте, так будет эффективней.

Если хотите, могу скинуть код моего перебора. Вот он:

Перебор

#include <bits/stdc++.h>

using namespace std;

vector <bool> p = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

bool check(int a) {
	vector <int> v;
	while (a > 0) {
		v.push_back(a % 10);
		if (a % 10 == 0) {
			return 0;
		}
		a /= 10;
	}
	for (int i = 0; i < v.size(); ++i) {
		for (int j = i + 1; j < v.size(); ++j) {
			if (gcd(v[i], v[j]) > 1 || !p[v[i] + v[j]]) {
				return 0;
			}
		}
	}
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	cout.setf(ios::fixed);
	cout.precision(10);

	int n;
	cin >> n;

	for (int i = 10; i < 10000000; ++i) {
		if (check(i)) {
			cout << i << endl;
			--n;
		}
		if (n == 0) {
			cout << i << endl;
			return 0;
		}
	}
	cout << "FAIL" << endl << n << endl;
}

→ Ответить

dnazirzhanov05

4 года назад, # ^ |

Огромное спасибо! Можете объяснить

vector p = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};

→ Ответить

gmusya

4 года назад, # ^ |

← Rev. 3 →

$$$p[i] = 0$$$, если число $$$i$$$ составное; $$$p[i] = 1$$$, если $$$i$$$ простое.

UPD. Ошибся, разумеется $$$0$$$ и $$$1$$$ не являются составными числами.

→ Ответить

veschii_nevstrui

4 года назад, # ^ |

Формально говоря, не так. $$$p[i] = 1$$$, если $$$i$$$ простое, и $$$p[i] = 0$$$ если $$$i$$$ не простое.

Вообще мне нужна была таблица простых чисел до $$$20$$$, но было очень лень реализовывать Эратосфена, поэтому я ее руками вбил.

→ Ответить

orangeorange

4 года назад, # |

Можно ссылку на задачу?

→ Ответить

dnazirzhanov05

4 года назад, # ^ |

https://olymp.krsu.edu.kg/ContestProblemset.aspx?contest=151 Задача Е.Кызыктуу сандар = Интересные числа. Если открыть задачу с формата (pdf).На первом листе киргизский вариант , а на следующем листе имеется русский вариант.

→ Ответить