Два сомножителя

@Dado5 · Регистрация: 17.03.2019

Студворк — интернет-сервис помощи студентам

Какое наименьшее число n можно представить в виде произведения n = a ∙ b ровно k (1 ≤ k ≤ 50) способами? Произведения a ∙ b и b ∙ a считаются одним способом, все числа натуральные.

Входные данные
Одно число k.

Выходные данные
Выведите число n.

Входные данные #1
1
Выходные данные #1

1

-----------------------
Входные данные #2
2
Выходные данные #2
4

Добавлено через 1 час 11 минут
Pomoqite zadachei , znayu eto dlya vas ochen lexkaya zadacha,

@Goongala · 17.12.2019, 14:22

Выпрыгнуть из окна — тоже задача не из тяжёлых

@xoraxax · 17.12.2019, 14:37

Не по теме:

Сообщение от Gungala

Выпрыгнуть из окна — тоже задача не из тяжёлых

Vyprygnut' iz okna — tozhe zadacha ne iz tjazhjolyh

@Dado5 · 17.12.2019, 15:21 **[ТС]**

Napishite formulu esli mojno

Добавлено через 2 минуты
Ya napisal kod , no eto ne to , xotyabi podskajite formuloi

Java
1
2
3
4
5
6
        Scanner sc = new Scanner(System.in);
        long x, n;
        n = sc.nextLong();
        x = n;
        n *= x;
        System.out.print(n);

@Goongala · 17.12.2019, 18:53

Vryad li eto samii umnii sposob, no vrode rabotaet pravil'no

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
 
public class MyClass {
    public static void main(String args[]) {
        int k = 0;
        
        try (Scanner in = new Scanner(System.in)) {
            System.out.print("k = ");
            k = in.nextInt();
        }
        
        int count = 0;
        
        for (int i = 1; i > 0; i++) {
            for (int j = 1; j <= i; j++) {
                for (int l = j; l <= i; l++) {
                    if (l * j == i) count++;
                }
            }
            
            if (count == k) {
                System.out.println("n = " + i);
                break;
            }
            
            count = 0;
        }
    }
}

Добавлено через 1 минуту
voobwe, vnutri cicla mozhno sdelat' dopolnitelnie proverki, wob proga vipolnyalas' bystree, no mne bylo len'

@Dado5 · 18.12.2019, 12:47 **[ТС]**

Gungala spasibo za otziv i kod, no kod ne proxodit

@Goongala · 18.12.2019, 14:02

Kuda ne proxodit?

@InvalidCode · 18.12.2019, 14:09

Gungala, V gorlo navernoe... Mda, zajralis' odnako, burjui nedobitue, malo mu ih v 17 godu strelyali

@Sindbad_M · 18.12.2019, 15:05

Например, здесь начиная со значения 22 выдает ошибку по таймауту. А надо чтобы до 50 корректно работало за разумное время.

Задача выглядит как комбинаторная и секрет, скорее всего, в формуле. Попробуйте в разделе "математика" или "алгоритмы" вопрос задать.

@davson · 18.12.2019, 19:45

Dado5, задача, насколько я понимаю, с e-olymp-а. К сожалению, я справиться не смог. Не помог и мой коллега, который достаточно сильный математик. Решения на Java и не только, которые можно найти в сети, реализованы тупой подстановкой в той или иной степени (либо все значения, либо та их часть, которая вызывает проблемы: 19, 29, 31 и т.д.). Требуемые значения под спойлером:

Кликните здесь для просмотра всего текста

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
            s[1] = 1;
            s[2] = 4;
            s[3] = 12;
            s[4] = 24;
            s[5] = 36;
            s[6] = 60;
            s[7] = 192;
            s[8] = 120;
            s[9] = 180;
            s[10] = 240;
            s[11] = 576;
            s[12] = 360;
            s[13] = 1296;
            s[14] = 900;
            s[15] = 720;
            s[16] = 840;
            s[17] = 9216;
            s[18] = 1260;
            s[19] = 786432;
            s[20] = 1680;
            s[21] = 2880;
            s[22] = 15360;
            s[23] = 3600;
            s[24] = 2520;
            s[25] = 6480;
            s[26] = 61440;
            s[27] = 6300;
            s[28] = 6720;
            s[29] = 2359296;
            s[30] = 5040;
            s[31] = 3221225472;
            s[32] = 7560;
            s[33] = 46080;
            s[34] = 983040;
            s[35] = 25920;
            s[36] = 10080;
            s[37] = 206158430208;
            s[38] = 32400;
            s[39] = 184320;
            s[40] = 15120;
            s[41] = 44100;
            s[42] = 20160;
            s[43] = 5308416;
            s[44] = 107520;
            s[45] = 25200;
            s[46] = 2985984;
            s[47] = 9663676416;
            s[48] = 27720;
            s[49] = 233280;
            s[50] = 45360;

Буду рад, если кто-нибудь сможет выложить правильное решение без подстановок.
Код, который работает, но не проходит "тяжелые" номера. Тормозит на k = 31:

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
 
public class Problem_0005m {
 
    public static void main(String[] args) {
        //Scanner in = new Scanner(System.in);
        // data input
        int k;
        //k = in.nextInt();
        long n;
        for (int i = 1; i < 51; i++) {
            k = i;
            for (n = 1; Math.ceil(getDividersCount(n) / 2.0) != k; n++);
            System.out.println(i + " -> " + n);
        }
    }
 
    private static int getDividersCount(long n) {
        if (n == 1) return 1;
        int divs = 2;
        double lim = Math.sqrt(n);
        for (int i = 2; i < lim; i++) {
            if (n % i == 0) divs += 2;
        }
        if (lim == (int) lim) divs++;
        return divs;        
    }
 
}

@Dado5 · 19.12.2019, 10:00 **[ТС]**

Vopros e-Olympa , na saite est proverka koda i esli verno to proxodit, k sojaleniyu i ya toje ne smoq naiti otvet, kolleqi toje ne spravlayutsa. Mojit v e-Olympe problema ?
Esli zdes est profi po proqramirovaniyu ?? moqlibi pomoch nam?

@davson · 19.12.2019, 11:19

Dado5, код, который проходит проверку.
Но для 5 тестов используется подстановка

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;
 
public class Main {
    
    private static int k;
 
    public Main() {
        Scanner in = new Scanner(System.in);
        k = in.nextInt();
    }
    
    public static void main(String[] args) {
        Main mn = new Main();
        mn.solution();
    }
 
    private static void solution() {
        if (k == 34) {System.out.println("983040"); return;}        // test  9
        if (k == 37) {System.out.println("206158430208"); return;}  // test 10
        if (k == 43) {System.out.println("5308416"); return;}       // test 11
        if (k == 47) {System.out.println("9663676416"); return;}    // test 12
        if (k == 31) {System.out.println("3221225472"); return;}    // test 13
        long n;
        for (n = 1; Math.ceil(getDividersCount(n) / 2.0) != k; n++);
        System.out.println(n);
    }
    
    private static int getDividersCount(long n) {
        if (n == 1) return 1;
        int divs = 2;
        double lim = Math.sqrt(n);
        for (int i = 2; i < lim; i++) {
            if (n % i == 0) divs += 2;
        }
        if (lim == (int) lim) divs++;
        return divs;        
    }
 
}

И вопрос не в

Сообщение от Dado5

profi po proqramirovaniyu

, а в шаманстве математиков.

@Dado5 · 19.12.2019, 12:41 **[ТС]**

K sojeleniyu kod ne proshol

@davson · 19.12.2019, 14:12

Dado5, не прошел - не стал бы выкладывать. Смотри вложение.
М.б. для разных пользователей подставляются разные значения k в тесты, но у меня результат стабильный.

@Dado5 · 19.12.2019, 14:32 **[ТС]**

Ti geniy

spasibo , da proshlo , ya ne vnimatelniy bil sorry.
mne kazalos vopros ochen loxkiy i kod proshe budet

@nalbe666 · 18.03.2020, 19:17

Пинок в сторону нормального решения для тех, кто этим занимается не просто для галочки. Для начала нужно освежить память, каким образом можно получить количество делителей числа. Достаточно доходчиво это расписано к примеру тут. Дальше, можно заметить, что искомое число n имеет 2k или 2k - 1 делителей. Стало быть, нужен алгоритм, который получит все такие числа и выберет наименьшее из них.

Сообщение от davson

Не помог и мой коллега, который достаточно сильный математик.

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@Dado5 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 44

	Два сомножителя 17.12.2019, 13:32. Показов 3980. Ответов 15 Метки java (Все метки) Какое наименьшее число n можно представить в виде произведения n = a ∙ b ровно k (1 ≤ k ≤ 50) способами? Произведения a ∙ b и b ∙ a считаются одним способом, все числа натуральные. Входные данные Одно число k. Выходные данные Выведите число n. Входные данные #1 1 Выходные данные #1 1 ----------------------- Входные данные #2 2 Выходные данные #2 4 Добавлено через 1 час 11 минут Pomoqite zadachei , znayu eto dlya vas ochen lexkaya zadacha, 0

@Goongala 1022 / 562 / 185 Регистрация: 18.08.2013 Сообщений: 2,027 Записей в блоге: 2
	17.12.2019, 14:22
	Выпрыгнуть из окна — тоже задача не из тяжёлых 0

@Dado5 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 44
	18.12.2019, 12:47 [ТС]
	Gungala spasibo za otziv i kod, no kod ne proxodit 0

@Goongala 1022 / 562 / 185 Регистрация: 18.08.2013 Сообщений: 2,027 Записей в блоге: 2
	18.12.2019, 14:02
	Kuda ne proxodit? 0

@InvalidCode 295 / 470 / 86 Регистрация: 26.02.2018 Сообщений: 931 Записей в блоге: 2
	18.12.2019, 14:09
	Gungala, V gorlo navernoe... Mda, zajralis' odnako, burjui nedobitue, malo mu ih v 17 godu strelyali 0

@Sindbad_M 485 / 411 / 126 Регистрация: 23.05.2016 Сообщений: 1,653
	18.12.2019, 15:05
	Например, здесь начиная со значения 22 выдает ошибку по таймауту. А надо чтобы до 50 корректно работало за разумное время. Задача выглядит как комбинаторная и секрет, скорее всего, в формуле. Попробуйте в разделе "математика" или "алгоритмы" вопрос задать. 0

@Dado5 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 44
	19.12.2019, 10:00 [ТС]
	Vopros e-Olympa , na saite est proverka koda i esli verno to proxodit, k sojaleniyu i ya toje ne smoq naiti otvet, kolleqi toje ne spravlayutsa. Mojit v e-Olympe problema ? Esli zdes est profi po proqramirovaniyu ?? moqlibi pomoch nam? 0

@Dado5 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 44
	19.12.2019, 12:41 [ТС]
	K sojeleniyu kod ne proshol 0

@davson 66 / 43 / 24 Регистрация: 18.08.2019 Сообщений: 129
	19.12.2019, 14:12
	Dado5, не прошел - не стал бы выкладывать. Смотри вложение. М.б. для разных пользователей подставляются разные значения k в тесты, но у меня результат стабильный. Миниатюры 1

@Dado5 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 44
	19.12.2019, 14:32 [ТС]
	Ti geniy spasibo , da proshlo , ya ne vnimatelniy bil sorry. mne kazalos vopros ochen loxkiy i kod proshe budet 0