Функция Эйлера от числа сочетаний

[Paul Ivanov]

Добрый день. На третью задачу убил очень много времени (хоть и решил её). Задумался о том, что решение получилось слишком эффективным (в итоге время ниже в 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);
}
 

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

[mihaild]

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

[Paul Ivanov]

Ну да, что-то не додумался по ходу.
например так:

Используется синтаксис C

int s=0;
for (int k = N / p; k > 0; k /= p) s += k;

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