Как посчитать количество чисел y, меньших либо равных N, представимых в виде произведения сомножителей из [p1,.. pK], каждый из сомножителей может входить в это произведение с произвольной степенью???

Здравствуйте, ioctl, Вы писали:

I>Как посчитать количество чисел y, меньших либо равных N, представимых в виде произведения сомножителей из [p1,.. pK], каждый из сомножителей может входить в это произведение с произвольной степенью???

закидывай на пивас — так уж и быть напишу тебе прогу ..

xma>закидывай на пивас — так уж и быть напишу тебе прогу ..

Мне не для работы, просто интересно.

Если не жалко, расскажи идею в 2х словах.

Здравствуйте, ioctl, Вы писали:

I>Если не жалко, расскажи идею в 2х словах.
Для небольших N самое простое пересчитать:

#!/usr/bin/lua

function count(p,N)
    local s,y,m
    local function next(r) r=r or 1
        if r>#p then return false end
        y=y*p[r] m[r]=m[r]*p[r] if y<=N then return true end
        y=y//m[r] m[r]=1 return next(r+1)
    end
    s=0 y=1 m={} for i=1,#p do m[i]=1 end    
    while next() do s=s+1 end
    return s
end

print( count({2,3,5},15) )

10

Здравствуйте, ioctl, Вы писали:

I>Мне не для работы, просто интересно.

жмот

I>Если не жалко, расскажи идею в 2х словах.

могут ли быть нулевые степени у членов массива ?

вообщем, считаем для каждого элемента массива — маскимальную степень в которой он меньше N ..

ну и далее фигачим для каждого элемента (начиная с первого) — от максимальной степени до нулевой, перемножая со вторым от максимальной_2 (которая в произведении — меньше N), и так далее со след числами

плюс "счётчик" (флаг) единиц (итогового числа) — после первой единицы — в общем количестве (чисел меньше N) их не учитываем

общая идея такова (ниже), код вроде верный — но как говорится кто его знает, если что "отладка решает" (c)

	Скрытый текст
	// предварительно считаем массив max_powers[K]; bool one_flag = false; // будем надеятся памяти для стека хватит, иначе перепишите в циклы // хватит ли int для степеней ? (скорректируете там под тот или иной класс "Big Number") int N_below_count( int number_total_prev, int new_number_index ) { if ( number_total_prev > N ) return 0; if ( new_number_index >= K ) return 0; // индексы с нуля const int max_power = find_max_power(number_total_prev, new_number_index); // тут элементарно, если бруте форсом int N = 0; if ( 0 == max_power ) { if ( 1 == number_total_prev && false == one_flag ) { // единицу учитываем - один раз ++N; one_flag = true; } return N; } int new_number = numbers[new_number_index]; if ( new_number_index == K-1 ) { if ( new_number > 1 ) N += max_power; if ( 1 == number_total_prev && false == one_flag ) { // единицу учитываем - один раз ++N; one_flag = true; } return N; } for (int power=max_power; power>=0; --power) { N += N_below_count( number_total_prev * pow(new_number, power), new_number_index + 1 ); } return N; } int main(){ int res = N_below_count(1, 0); // индексы с нуля, числа в массиве - не меньше единицы }

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

ну и понятно, считаем что дубликатов — в массиве исходном нету

Здравствуйте, xma, Вы писали:

xma>вообщем, считаем для каждого элемента массива — маскимальную степень в которой он меньше N ..
xma>ну и далее фигачим для каждого элемента (начиная с первого) — от максимальной степени до нулевой, перемножая со вторым от максимальной_2 (которая в произведении — меньше N), и так далее со след числами
xma>плюс "счётчик" (флаг) единиц (итогового числа) — после первой единицы — в общем количестве (чисел меньше N) их не учитываем
И чем это лучше банального счета по порядку?
N=15 p={2,3,5}

       2 3 5
 1    {1,0,0}=2
 2    {2,0,0}=4
 3    {3,0,0}=8
 4    {0,1,0}=3
 5    {1,1,0}=6
 6    {2,1,0}=12
 7    {0,2,0}=9
 8    {0,0,1}=5
 9    {1,0,1}=10
10    {0,1,1}=15

xma>общая идея такова (ниже), код вроде верный — но как говорится кто его знает, если что "отладка решает" (c)

xma> ...
xma> if ( new_number_index = K-1 ) 
xma> ...

Здравствуйте, kov_serg, Вы писали:

_>И чем это лучше банального счета по порядку?

напиши алгоритм, так не понятно ..

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

xma>> if ( new_number_index = K-1 )

да, косячок зато бесплатно "тогда мне два пирожка с капустой и четыре с говном" (c) ..

Здравствуйте, xma, Вы писали:

_>>И чем это лучше банального счета по порядку?

xma>напиши алгоритм, так не понятно ..
Так уже выше написал. Вот вариант с отображением происходящего

function count_dbg(p,N)
    local s,x,z,y,inc=0,1,{},{}
    for i=1,#p do z[i]=1 y[i]=0 end
    function inc(r)
        if r>#p then return false end
        x=x*p[r] z[r]=z[r]*p[r] y[r]=y[r]+1
        if x<=N then return true end
        x=x//z[r] z[r]=1 y[r]=0 
        return inc(r+1)
    end
    local function line(y) local s="" for i=1,#y do if i>1 then s=s.."," end s=s..y[i] end return s end
    while inc(1) do
        s=s+1
        print(s,"{"..line(y).."}="..x)
    end
    return s
end

1    {1,0,0}=2
2    {2,0,0}=4
3    {3,0,0}=8
4    {0,1,0}=3
5    {1,1,0}=6
6    {2,1,0}=12
7    {0,2,0}=9
8    {0,0,1}=5
9    {1,0,1}=10
10    {0,1,1}=15
10

xma>у меня вроде как и так оптимальный вариант — в циклы конечно можно запихать но уже всё не столь очевидно будет
Вот оптимизированный вариант (но выигрыш так себе, только в специфических случаях)

#!/usr/bin/lua

function logi(n,p)
    local r,q=0,p*p
    if q<=n then r,q=logi(n,q) r=2*r else q=1 end
    if q*p<=n then r=r+1 q=q*p end
    return r,q
end
function count(p,N,n) n=n or #p
    if N<=1 or n<1 then return 0 end
    if n==1 then return logi(N,p[n]) end
    local s,x,xs=count(p,N,n-1),p[n]
    while x<=N do
        s=s+1 xs=count(p,N//x,n-1)
        if xs==0 then break end
        s=s+xs x=x*p[n]
    end
    return s
end

print( count ({2,3,5},15) )

10

Здравствуйте, kov_serg, Вы писали:

xma>>напиши алгоритм, так не понятно ..
_>Так уже выше написал. Вот вариант с отображением происходящего

я на тарабарском — не понимаю ..

Здравствуйте, xma, Вы писали:

xma>я на тарабарском — не понимаю ..
так лучше ?

typedef unsigned long long num;

struct Count {
    int n; num N,y,*p,*m;
    Count(int n,num *p,num *m) : n(n),p(p),m(m) { N=0; y=0; }
    void reset(num N) { this->N=N; y=1; for(int i=0;i<n;i++) m[i]=1; }
    int next(int r=0) {
        if (r>=n) return 0;
        y*=p[r]; m[r]*=p[r]; if (y<=N) return 1;
        y/=m[r]; m[r]=1; return next(r+1);
    }
    void show(num s);
    num count(num N) { 
        num s=0; reset(N); 
        while(next()) { s++; show(s); }
        return s;
    }
};

#include <iostream>
static num mf(num n,num p) { num r=0; while(n%p==0) { n/=p; r++; } return r; }
void Count::show(num s) {
    std::cout<<s<<"\t{";
    for(int i=0;i<n;i++) { if (i>0) std::cout<<","; std::cout<<mf(y,p[i]); }
    std::cout<<"}="<<y<<std::endl;
}

int main(int argc, char const *argv[]) {
    enum { n=3, N=15 }; num p[n]={ 2,3,5 }, m[n];
    std::cout<<Count(n,p,m).count(N)<<std::endl;
    return 0;
}

1    {1,0,0}=2
2    {2,0,0}=4
3    {3,0,0}=8
4    {0,1,0}=3
5    {1,1,0}=6
6    {2,1,0}=12
7    {0,2,0}=9
8    {0,0,1}=5
9    {1,0,1}=10
10    {0,1,1}=15
10

ps: Настоящий физик может писать фортраном на любом языке

Здравствуйте, kov_serg, Вы писали:

_> y*=p[r]; m[r]*=p[r]; if (y<=N) return 1;
_> y/=m[r]; m[r]=1; return next(r+1);

чем в таком скопище говна разобраться, проще — сравнить с эталонным алгоритмом (предварительно его конечно проверив), и далее — на больших наборах данных и произвольных рандомных числах (простых) и (включая) относительно больших N .. (со специальными классами "Big Number", чтоб не упереться в лимиты int и long), главное в память не упираясь и в долгие расчёты ..

но мне лень ..

_>ps: Настоящий физик может писать фортраном на любом языке

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

вообще, теперь становится понятным — сложности поиска работы программистом у научных сотрудников, ибо можно предположить — что с простым/понятным и поддерживаемым кодом у них бяда, и понятно что после их ухода — в программерской конторе наступит апокалиптец ..