2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Функция Эйлера от числа сочетаний
Сообщение19.02.2021, 21:06 


23/04/18
143
Добрый день. На третью задачу убил очень много времени (хоть и решил её). Задумался о том, что решение получилось слишком эффективным (в итоге время ниже в 500 раз требуемой верхней границы - 6 ms, и память ниже в 100 раз - 2.34 mb)и, наверное можно было сделать проще сильно сэкономив время.
Собственно прикладываю свой код и буду благодарен за любой совет, как изменить акценты в подходе к решению подобного рода задач и вообще каким должно бы было быть решение, чтобы на написание кода ушло минимальное время, так как времени на продумывание кода и отладку ушло больно много.
(заранее извиняюсь, если в комментариях недостаточно подробно описал процесс собственно вычисления ответа, если что-то не понятно, скажите - исправлю).
Ссылки на описание задачи:
https://ibb.co/drTRSjT
https://ibb.co/VqNzvt5
код: [ скачать ] [ спрятать ]
Используется синтаксис C
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include <cstdlib>
typedef long long int llint;
const int Q = 1000000;
const int Mr = 1000000007;

int multiple(int a, int b) {
        return (int)(((llint)a * (llint)b) % Mr);
}
int prime(int MAX, int* M) {
        int* B = (int*)malloc((MAX + 1) * sizeof(int)); //массив нулей и единиц, в котором ноль это составное, а 1 - простое число
        B[1] = 0;
        for (int i = 2; i <= MAX; i++) {// делаем все числа простыми по умолчанию
                B[i] = 1;
        }
        int i = 2, p = 0;
        while (i < ceil(sqrt(MAX))) {// вычеркиваем по решету эратосфена до квадратного корня из MAX попутно заполняя M
                while (!B[i]) i++;
                for (int i1 = 2 * i; i1 <= MAX; i1 += i) B[i1] = 0;
                M[p] = i;
                p++;
                i++;
        }
        while (i <= MAX) { // заканчиваем заполнение M
                if (B[i]) {
                        M[p] = i;
                        p++;
                }
                i++;
        }
        return p;
        free(B);
}
int main() {
        int MAX = 500000;
        int* M = (int*)malloc(Q * sizeof(int)); // M - массив простых чисел
        int L=prime(MAX, M);// L - количество простых чисел до MAX
        int* T = (int*)malloc(L * sizeof(int));// сокращаем массив для экономии памяти
        for (int i = 0; i < L; i++) T[i] = M[i];
        free(M);
        M = T;
        int K, N;
        scanf("%u %u", &K, &N);
        int* R = (int*)calloc(L, sizeof(int)); // R - накопительный массив для степеней простых чисел в итоговом разложении биномиального коэффициента
        for (int i = 0; i < L; i++) {// первый цикл накапливает степени простых чисел для множителей от N-K+1 до N в числителе
                int i1 = M[i], s = 0;
                while (1) {
                        int c = N - K + i1 - ((N - K) % i1); //c - первый множитель в диапазоне, делящийся на i1
                        if (c <= N) s += (N - c) / i1 + 1;
                        else break;
                        if ((llint)i1 * (llint)M[i] > (llint)500000) break; // учитываем возможное переполнение int
                        i1 *= M[i];
                }
                R[i] = s;
        }
        for (int i = 0; i < L; i++) {// второй цикл обрабатывает диапазон множителей от 1 до K в знаменателе
                int i1 = M[i], s = 0;
                while (1) {
                        int c = i1;
                        if (c <= K) s += (K - c) / i1 + 1;
                        else break;
                        if ((llint)i1 * (llint)M[i] > (llint)500000) break;
                        i1 *= M[i];
                }
                R[i]-= s;
        }
        int z = 1;
        for (int i = 0; i < L; i++) { // здесь и далее собственно вычисляем функцию эйлера по модулю Mr
                if (R[i] > 0) {
                        R[i]--;
                        z = multiple(z, M[i] - 1);
                }
        }
        for (int i = 0; i < L; i++) {
                for (int i1 = 0; i1 < R[i]; i1++) z = multiple(z, M[i]);
        }
        printf("%u", z);
        free(M);
        free(R);
}
 


 i  Lia: название темы изменено на содержательное. Здесь в скрине не было никакой необходимости. Воспроизводите условие задачи в тексте сообщения.

 Профиль  
                  
 
 Re: ещё одна ол. зад., в этот раз решённая, просто прошу совета
Сообщение19.02.2021, 21:11 
Заслуженный участник
Аватара пользователя


16/07/14
8337
Цюрих
Попробуйте подумать, как посчитать степень, в которой данное простое входит в факториал данного числа. Это пишется примерно в 1-2 строчки кода.

 Профиль  
                  
 
 Re: ещё одна ол. зад., в этот раз решённая, просто прошу совета
Сообщение19.02.2021, 21:34 


23/04/18
143
Ну да, что-то не додумался по ходу.
например так:
Используется синтаксис C
int s=0;
for (int k = N / p; k > 0; k /= p) s += k;

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group