Как можно оптимизировать решение данной задачи?

@NuMeRiC_ · Регистрация: 03.06.2019

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

Всем привет!
Есть задачка, вот условие:

Напишите функцию, которая принимает в качестве параметра целое число n и возвращает true, если число n! % (n^2) == 0.

Вроде все понятно, вот только задача непростая, ведь максимум n, для которого она хоть что-либо может предложить(если делать по-простому, то есть считать каждое выражение), это примерно 20-25. Дальше все.

Поэтому вот алгоритм, по которому делал я:

Разбил число n ^ 2 на делители, поместил в масив nPw. Разбил числа от 1 до n на делители, поместил в values. Вычеркнул общие члены для массивов; если в nPw остались элементы, то число n! не делится на n ^ 2.
Если что, вот код:

C++
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
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
 
//Primes() accepts certain number and returns and returns its expanded version(on primes) like vector.
 
vector<int> Primes(int n) {
    vector <int> v;
    while (n != 1) {
        for (int i = 2;; i++) {
            if (n % i == 0) {
                n /= i;
                v.push_back(i);
                break;
            }
        }
    }
    return v;
}
 
bool Factorial(int n) {
    //--------------------------------------------
    auto nPw = Primes(n*n); //now nPw contains all prime dividers of n^2
    //--------------------------------------------
    vector<int> values; values.reserve(n); //Vector values for storing all dividers of n!
    //--------------------------------------------
    for (int i = 1; i <= n; i++) {
        auto tmp = Primes(i);   //tmp stores all dividers of i
        move(tmp.begin(), tmp.end(), inserter(values, values.end()));   //moving tmp to the end of the values
    }
    //--------------------------------------------
    //Deleting all common dividers of n^2 and n!
    for(int i = 0; i != nPw.size(); i++){
        for(int j = 0; j != values.size(); j++){
            if (nPw[i] == values[j]) {
                nPw.erase(nPw.begin() + i);
                values.erase(values.begin() + j);
                i--; j--;
                break;
            }
        }
    }
    //--------------------------------------------
    return nPw.size() == 0;
}

Но проходит только половину тестов, все остальное - исчерпан лимит времени, а последнее, так вообще ошибка исполнения.
Подскажите, плиз, как можно оптимизировать алгоритм и почему, как вы думаете, вылазит ошибка?

@XLAT · 09.01.2020, 19:40

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

n = 1318, 2800;

Результат TRUE.
А что должно то быть?

@COKPOWEHEU · 10.01.2020, 12:07

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

Результат TRUE.
А что должно то быть?

TRUE и должно быть. А ваш код выдает 0:

C
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
#include <stdio.h>
 
char XLAT(int n){
  int r = 1;
  int nn = n * n;
  for(int i = 1; i <= n; i++){
    r *= i;
    r %= nn;
    if(r == 0) return 1;
  }
  return 0;
}
 
int gcd(int a, int b){
  while(a > 0 && b > 0){
    if(a > b){
      a %= b;
    }else{
      b %= a;
    }
  }
 return a + b;
}
 
char COKP(int n){
  int nn = n;
  for(int i=2; i<nn; i++){
    n /= gcd(n, i);
    if(n == 1)break;
  }
  return (n==1);
}
 
int main(){
  int n = 1318;
  printf("XLAT: %i\nCOKP: %i\n", XLAT(n), COKP(n));
}

Code
1
2
3
4
$ gcc main.c
$ ./a.out 
XLAT: 0
COKP: 1

Добавлено через 27 минут
Интересным образом работает даже проверка числа на простоту. Точного математического доказательства у меня пока нет, но если число n является составным, оно проходит почти все тесты, кроме 1 и 4, по крайней мере до 100`000, причем делает это мгновенно (9 мс против 76 сек моего предыдущего варианта). В связи с этим два вопроса: Почему оно работает? Почему оно не работает на четверке?

Добавлено через 1 час 11 минут
Попытаюсь подвести теорию и алгоритм под вычисление через простые числа.
Случай первый: n - простое. Чтобы n! делилось на n² надо чтобы (n-1)! делилось на n, то есть из множителей 1...(n-1) можно было собрать n. Но n - простое, а значит по определению не может быть представлено как произведение. Следовательно, (n-1)! на n не делится, ответ - FALSE.
Случай второй: n - составное, то есть n=a*b, где 1<a,b<n. Если a!=b, то оба эти числа входят в последовательность факториала, а значит факториал делится на оба этих числа, а значит, и на n. Если же a==b, то чуть сложнее, ведь каждое число из последовательности входит в факториал только по одному разу. Но число может туда входить как сомножитель другого числа, то есть c = b*k, причем b=a ; k>1 ; 1<c<n, что эквивалентно b*k<n. Наименьшее k, которое может удовлетворять этому условию, равно 2. Подставляем n=a*b = a². 1<a,b<n => a,2a < n => 2a<n => 2a<a² => a>2. Таким образом, даже если оба сомножителя равны (n является квадратом), единственный случай, когда условие задачи не будет выполнено = квадрат двойки. Иначе говоря, число 4 - единственное исключение для квадратов.
Результат: (n-1)! делится на n без остатка в любом случае за исключением простых n и n==4.
В виде кода это выглядит так:

C
1
2
3
4
5
6
7
char COKP2(int n){
  int nn = sqrt(n)+1;
  for(int i=2; i<nn; i++)
    if((n % i) == 0)return (n!=4);
  if(n == 1)return 1;
  return 0;
}

и выполняется практически мгновенно без всякого кеширования.

Байт · 10.01.2020, 12:40

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

Попытаюсь подвести теорию и алгоритм под вычисление через простые числа.

Да, все верно. Вот этот кусочек

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

c = b*k, причем b=a ; k>1 ; 1<c<n,

можно изложить чуть попроще. Пусть n = b². Возьмем c = b*2. Тогда c < n за исключением случая n = 4 = 2*2

@XLAT · 10.01.2020, 13:07

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

А ваш код выдает 0:

хм,
я уже написал, что выдает мой код,
но ради вас повторюсь: на 1318, 2800 он выдает TRUE.

Обратите внимание, что не 1, и не 0, и не true,
а именно:
большими буковками TRUE

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
 
typedef long long UINT;
 
bool foo(UINT n)
{   UINT r = 1;
    UINT nn = n * n;
    for(UINT i = 1; i <= n; i++)
    {   r *= i;
        r %= nn;
        if(r == 0) return true;
    }
    return false;
}
 
int main()
{   
    UINT 
    n = 1318;
    std::cout << n << ":\t" << (foo(n) ? "TRUE" : "FALSE") << "\n";
         
    n = 2800;
    std::cout << n << ":\t" << (foo(n) ? "TRUE" : "FALSE") << "\n";
}

@COKPOWEHEU · 10.01.2020, 13:56

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

С типом данных int

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

typedef long long UINT;

Вообще-то я был удивлен, что для int, о котором и шла речь, переполнение произошло всего-то на 1318.
Да даже long long переполниться может. Например, как вам 9223372036854775783? Сейчас поищу еще чиселки поменьше

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

Обратите внимание, что не 1, и не 0, и не true,
а именно:
большими буковками TRUE

Уж извините, в данном случае мне интереснее математика и программирование, а не красивости.

Байт · 10.01.2020, 18:48

COKPOWEHEU, Можно сформулировать такую "теорему"
Число n > 4 является простым тогда и только тогда, когда (n-1)! не делится на n
Доказательство в вашем посте 22
Эквивалентная формулировка (возвращаясь к стартовому посту)
Число n > 4 является простым тогда и только тогда, когда n! не делится на n²

@COKPOWEHEU · 10.01.2020, 22:24

Сообщение от Байт

COKPOWEHEU, Можно сформулировать такую "теорему"

Может и можно (тонкие места в формулировке не выискивал) - но зачем?
Фактически, вы сформулировали теорему, обратную моей: "число n! делится на n² без остатка тогда и только тогда, когда оно не является простым и не равно 4".

Байт · 10.01.2020, 22:42

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

вы сформулировали теорему, обратную моей:

Что в лоб, что по лбу

Теорема ровно та же, но другими словами.
Впрочем, дальше уже скучно...

@COKPOWEHEU · 11.01.2020, 02:31

Сообщение от Байт

Впрочем, дальше уже скучно...

Согласен. Алгоритма эффективнее проверки на простоту вряд ли найдется. Даже с учетом того, что ТСу это решение не нужно.

Новые блоги и статьи Все статьи Все блоги /
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	10.01.2020, 18:48
	COKPOWEHEU, Можно сформулировать такую "теорему" Число n > 4 является простым тогда и только тогда, когда (n-1)! не делится на n Доказательство в вашем посте 22 Эквивалентная формулировка (возвращаясь к стартовому посту) Число n > 4 является простым тогда и только тогда, когда n! не делится на n² 0

Как можно оптимизировать решение данной задачи?

Решение