Найти начальное и конечное числа [требует правки]

410

18 января 2017, 00:29

Помогите пожалуйста с этим заданием ! Нет идей как можно решить .

Петя и Вася готовились к аттестации по теме "Умножение". Петя задумывал произведение всех натуральных чисел от A до B, а Вася старался угадать начальное и конечное числа. Помогите Васе найти значения A и B. Если решений несколько, выведите то, у которого A наименьшее.

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

Одно число – произведение чисел. 1 < A ≤ B ≤ 10000. Выходные данные

В одной строке через пробел два числа: A и B.

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

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

3 5

Answer 1

В общем раз всё равно написал код в комментарии, оформлю ответом.

char z[40000];
long long mod(long long mm){
    long long r = 0;
    for (int i=0; z[i]; i++){
        r %= mm;
        r*=10;
        r+= z[i] - '0';
    }
    return r%=mm;
}
int main ()
{
    gets(z);
    long long R[2];
    R[0] = mod(1000000000039LL);
    R[1] = mod(999999999989LL);
    for (int i=2;i<=10000;i++){
        long long Q[2] = {1,1};
        for (int j=i;j<=10000;j++){
            Q[1] *= j;
            Q[1] %= 999999999989LL;
            Q[0] *= j;
            Q[0] %= 1000000000039LL;
            if (Q[0] == R[0] && Q[1] == R[1]){
                printf("%d %d",i,j);
                return 0;
            }
        }
    }
}

Просто вычисляем произведение по модулю. В нормальных задачах советую использовать ~10 простых числе для вычисления модулей.

P.S. тесты настолько слабые что можно обойтись вычислением по 1 модулю вместо многих.