FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Ferko
Člen
Avatar
Ferko:5.3.2018 17:06

Ahoj,
mám problém s jedným programom:
Máme pole n čísel <1..100> a q otázok. Každá otázka je tvorená troma číslami (o,d,m). Pre každú otázku treba napísať (súčin čísel ležiacich v poli na pozíciach o až o+d-1) mod m.

Problém je, že n môže byť aj 105, čo zapríčiní, že súčin sa nezmestí ani do long a BigInteger je pomalý.

Nenapadá vás nejaké rozumnejšie riešenie?

Ďakujem

Príklad princípu v Pythone:

for i in range(q):
    o,d,m=input().split()
    o,d,m=int(o),int(d),int(m)
    s=1
    for j in range(o-1,o+d-1):
       s*=p[j]
    print(s%m)
Editováno
 
Odpovědět
5.3.2018 17:06
Avatar
DHPICO
Tvůrce
Avatar
Odpovídá na Ferko
DHPICO:5.3.2018 17:42

když se ti to nejvejde do Long, tak můžeš rozložit výpočet a ukládat si to do Stringu, ale nedokážu říct, zda to je rychlejší než BigInteger

Nahoru Odpovědět
5.3.2018 17:42
Požehnáni budíš oráj
Avatar
krepsy3
Tvůrce
Avatar
krepsy3:5.3.2018 17:58

BigInteger je, alespoň v .NETu, velmi dobře optimalizovaná struktura. Zároveň je bezpečná a spolehlivá. Nevím, zda by specificky tento úkol šel matematicky udělat nějakou rychlejší cestou přes string, nicméně bych ti doporučil bigint.

Zamyslím-li se, tak jako zrovna 105 je celkem v pohodě, protože je to ta desítka, za kterou se ti kumulují nuly, jak víc a víc násobíš, takže by to šlo řešit cestou "dvojího násobení" - v hlavní cestě násobíš čísla a odtrhuješ nulové řády, jejichž exponent pak násobíš v té druhé cestě, a ve finálním výpisu to dáš dohromady. Teoreticky by se tato možnost dala aplikovat na jakákoliv čísla ve "věděcké notaci" a ukládat do typu double, ale hrozilo by znepřesnění výpočtu kvůli desetinné čárce, pokud by čísel bylo moc.

P.S. Vědecká notace = 3278.2 = 3.2782e3 = 3.2782 * 103

Editováno
Nahoru Odpovědět
5.3.2018 17:58
Programátor je stroj k převodu kávy na kód.
Avatar
Jindřich Máca
Tvůrce
Avatar
Jindřich Máca:5.3.2018 18:13

Pánové, opravdu? :D Jelikož tohle je typický "školní" příklad, tak trik je čistě matematický. Čísla řádu 105, dokonce i vynásobená mezi sebou, se do long bohatě vejdou a víc nepotřebujete, protože Základní pravidla modulární aritmetiky. :-`

Můžete modulovat po každém násobení, dokonce každé to číslo samotné před tím násobením, což většinou značně sníží jeho řád, a pokud modulujete všechno stejným číslem, celkový výsledek se nezmění. ;)

Editováno
 
Nahoru Odpovědět
5.3.2018 18:13
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Ferko
Patrik Valkovič:5.3.2018 18:17

Malá fermatova věta
Eulerova věta

Editováno
Nahoru Odpovědět
5.3.2018 18:17
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ferko
Člen
Avatar
Odpovídá na Jindřich Máca
Ferko:5.3.2018 18:39

Ďakujem, toto by teda malo fungovať?

s:=1;
  for j:=a to a+x-1 do begin
    s*=k[j];
    s:=s mod m;
    end;
  writeln(s mod m);
  end;

alebo aj toto?

for j:=a to a+x-1 do s*=(k[j] mod m);
 
Nahoru Odpovědět
5.3.2018 18:39
Avatar
Jindřich Máca
Tvůrce
Avatar
Odpovídá na Ferko
Jindřich Máca:6.3.2018 0:33

Lépe bude fungovat to první, protože v tom druhém Ti s bude pořád narůstat, i když o něco pomaleji a na konci ho pak musíš ještě zmodulovat do výsledné podoby. Naopak u toho prvního držíš celé s pravidelnou modulací v přiměřeném rozsahu a po skončení cyklu už ho ani modulovat nemusíš. ;)

Pro jistotu tedy:

s:=1;
  for j:=a to a+x-1 do begin
    s*=k[j];
    s:=s mod m;
    end;
  writeln(s); # s již prošlo mod na konci cyklu
  end;

P.S.: Nejlepší bude, když si sám napíšeš nějakou krátkou řadu malých čísel a zkusíš si to spočítat, jestli to sedí. :)

 
Nahoru Odpovědět
6.3.2018 0:33
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.