Умножение

[pax]

Не помню, былали тут такая загадка, в общем сабж:
http://tpas.gym5cheb.ru/p6aa1.html
5.2.Эффективные алгоритмы.

Задание для тренировки.

1.Дано вещественное число А. Не пользуясь никакими арифметическими операциями, кроме умножения, получить:
8 ) А^19 за пять операции;

Голову сломали и подумали что это троллинг такой) Но может есть ответ?

[SBJoker]

У меня только за 6 операций получается

[pax]

Да, за шесть легко...

[radiobutton]

1) А^4 за две операции;
2) А^6 за три операции;
3) А^7 за четыре операции;
4) А^8 за три операции;
5) А^9 за четыре операции;
6) А^13 за пять операции;
7) А^15 за пять операции;
8) А^19 за пять операции;
9) А^21 за шесть операции;
10)А^28 за шесть операции;

Больше похоже на опечатку. Ибо остаьлные решаются мгновенно.

[pax]

Задача встречается в разных задачниках с такой же формулировкой...

[radiobutton]

Сообщение от pax

Задача встречается в разных задачниках с такой же формулировкой...

окей. какая то хитрость скрыта значит. как будит время подумаю посерьезней =)

хотя:
С такой:

1) А^4 за две операции;
2) А^6 за три операции;
3) А^7 за четыре операции;
4) А^8 за три операции;
5) А^9 за четыре операции;
6) А^13 за пять операции;
7) А^15 за пять операции;
А^19 за пять операции;
9) А^21 за шесть операции;
10)А^28 за шесть операции;
?

или с такой:

А^19 за пять операции?

[pax]

формулировка встречалась так же как и в том задачнике, что я ссылку дал. Но интересует как раз А^19 за пять операции

[radiobutton]

A*B % С = A^0.75 % С

Нужно решить это уравнение. (С констранта). Нужно найти B. Причем чтобы оно не зависело от А.

Либо такое:
((A^N) * B) % C = 1 % C (C и N константы)

[impersonalis]

У кого ни спрашивал - все приводили различные реализации в 6 действий.

[pax]

Да видно все таки троллинг такой.

[den]

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

[Igor]

ради интереса написал программку, которая считает минимальное количество ходов.
Перебором.
Эх, 19 можно только за шесть((
Перемножая числа, по сути, складываем степени.
Вот код на сях:

#define len 10

int bestLen=len;
void print(int ar[],int pos){
    if (pos<bestLen){
        bestLen=pos;
        for(int i=0;i<=pos;i++)
            printf("%i,",ar[i]);
        printf("\n");
    }
}

void allVariants(int ar[],int pos,int num){
    if (pos>=bestLen) return;
    for(int i=pos-1;i>=0;i--)
        for(int j=i;j<pos;j++){
            int res=ar[i]+ar[j];
            if (res>ar[pos-1]){
                ar[pos]=res;
                if (ar[pos]==num)
                    print(ar,pos);
                if (ar[pos]<num)
                    allVariants(ar,pos+1,num);
            }
        }
}

int vect[len];
int main(){
    vect[0]=1;
    for(int i=2;i<65;i++){
        allVariants(vect,1,i);
        printf("num = %i,best len = %i \n",i,bestLen);
        bestLen=len;
    }
    getchar();
    return 0;
}