Количество прогрессий в интервале

Question

В файле дано три целых числа ?, ? и ?. Требуется найти количество возрастающих арифметических прогрессий, у которых ровно ? элементов лежит в диапазоне от ? до ? включительно. В данной задаче нужно рассматривать только прогрессии, у которых все элементы целые. Считается, что у арифметической прогрессии есть первый элемент, но нет последнего: она бесконечная. Если две прогрессии начинаются с разного элемента, то их нужно считать различными. Достаточно долго бьюсь с кодом, но получается какая-то ерунда... Посоветуйте, что можно сделать/исправить, пожалуйста :)

#include<stdio.h>
#include<math.h>
int main(){
    int L, R, K, N, i, a, b;
    N=0;
    scanf("%d %d %d", &L, &R, &K);
    if(K==1){
        N=R-L;
    }
    else if (K>1){
        b=ceil((R-L)/(K-1));
        for(i=0; i<=(R-L); i+=b){
            if((i>=L)&&((i+(K-1)*b)<L))
                N++;
        }
        
        
    }
    printf("%d", N);
}

Answer 1

Не ответ! но в комментарий не помещаюсь :(

Ну, давайте подумаем. Итак, что такое прогрессия? Это числа

a, a+b, a+2b ... a+(K-1)b ...

(Тут показано ровно K членов) Какие условия накладывает задача? Первый и последний элемент должен быть внутри диапазона, а перед первым и после последнего - вне.

Т.е.

a >= L
a +(K-1)b <= R
a-b < L
a+Kb > R
b > 0

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

Кстати, для простоты, не меняя общности, можно считать, что ищем количество в диапазоне от 0 до R-L.

Из приведенных уравнений получаем, что

(R-L)/(K-1) >= b > (R-L)/(K+1)

Ну, и

0 <= a <= R-L-(K-1)*b
a > R - K*b

Значит, навскидку

int Count(int L, int R, int K)
{
    R-=L;
    int count = 0;
    for(int b = R/(K-1); b > R/(K+1); --b)
    {
        int a = R-K*b;
        if (a < 0) a = 0;
        int aa = R - (K-1)*b;
        if (aa-a > 0) count += aa-a;
    }
    return count;
}

Попробуйте, может, чего и не учел...

Answer 2

Во-первых, не

Если две прогрессии начинаются с разного элемента, то их нужно считать различными.

А если эти разные элементы, с которых они начинаются, взаимнопросты.

Иначе, если найдется хотя бы одна прогрессия, их сразу же найдется и бесконечность, потому что:

a, a + b, a + 2b, ...
a - b, a, a + b, a + 2b, ...
a - 2b, a - b, a, a + b, a + 2b, ...
⋮

"пройдут" по одинаковым элементам.

Во-вторых, @Harry видимо всё правильно написал. У меня получилось так:

int Count(int L, int R, int K)
{
    R -= L;
    int count = 0;
    for(int b = R / (K - 1); R / b < K + 1; --b)
    {
        if (R / b < K)
            count += 1 + R % b; // учитываем прогрессию + её все возможные "сдвиги"
        else
            // максимально сдвинуть прогрессию можно на b - 1 (иначе в диапазон залезет элемент слева)
            // минимально прогрессию необходимо сдвинуть на R % b + 1, чтобы сдвинуть K + 1 'ый элемент за правую границу диапазона
            // итого, b - 1 - (R % b + 1) сдвигов
            // так как включительно, +1
            count += b - 1 - (R % b + 1) + 1;
    }
    return count;
}

Answer 3

Учитывая понятное теперь благодаря комментариям условие:

int Count(int L, int R, int K)
{
    R -= L;
    int count = 0;
    while (R > 0)
    {
        count += R / (K - 1) - R / K;
        --R;
    }
    return count;
}

Answer 4

короче говоря, вот какое решение оказалось верным

#include <stdio.h>
int main()
{
int L, R, K, i, d, j, k, a1, a2;
scanf ("%d %d %d", &L, &R, &K);
a1=a2=d=k=0;
d=R-L;
for (j=1; j<=d; j++)
{
    for (i=L; i<R; i++)
    {
     a1 = i+j*(K-1);
     a2 = i+j*K;
     if ((a1<=R) && (a2>R) )
     k=k+1;
    }
}
printf ("%d", k);
    return 0;
}

БЛОГ НА HUSL

Количество прогрессий в интервале

Ответы (4 шт):