Evo, stvarno vise nemam ideje za ovaj zadatak, pa je svaka pomoc dobrodosla... Moje razmisljanje do sada :
1+A+{A}^{2}+{A}^{3}+...+{A}^{n} = X |: {A}^{n} ( A > 1 )
{\left( \frac{1}{A}\right)}^{n} + {\left( \frac{1}{A}\right)}^{n-1} + {\left( \frac{1}{A}\right)}^{n-2} + ... + 1 = \frac{X}{{A}^{n}}\\
\frac{1-\left({\frac{1}{A}\right)}^{n+1}}{1-\left(\frac{1}{A}\right)} = \frac{X}{{A}^{n}}\\
jos\ kad\ se\ sad\ sve\ pomnozi\ sa\ nazivnikom:\\
X=\frac{{A}^{n+1}-1}{A-1}
.. i sad ovo samo izracunati mod m ... Ali dobivam WA za svaki input ...
Si siguran da mozes da modiras pa da delis?
Hm... Mozda ako su A i X BigNum-ovi, pa se primeni algoritam brzog stepenovanja na ovaj poslednji izraz koji je dpetek napisao?
Moze li ta ideja proci?
Pa moze ako istepenuje A^(n+1) pa da nekako brzo podeli sa A-1, zanimljivo, valja probati :D
A kako da podeli brzo?
Mislim da je ono "rucno" deljenje (kao na papiru) dovoljno brzo... :-S
nisam radio na taj nacin taj zadatak, ali kad pricate o tome dijeljenju, nije vam potreban bignum, mozete izracunati i brojnik i nazivnik po modulu M..pa onda to srediti na vec poznate nacine
Mislim, zadatak je mnogo laksi ako se samo rastavi, al nevezano za to, nisam siguran da samo moze po modulu m, razmislicu malo :D
Ja sam rucno probao za nekoliko test primjera, i ispala su mi dobra rjesenja... Mozda mi je to slucajno točno izašlo...
Nacin na koji sam racunao:
brojnik = ({A}^{n+1} + m-1)\ mod\ m
nazivnik = (A + m -1 )\ mod\ m;
Edit: Eh, sry ... zaboravio sam da je forum na engleskom...
a sto ako ti se desi da je brojnik manji od nazivnika..nece bit dobra rjesenja..
Da, ako i valja, onda ako je manji brojilac moras da mu dodajes m dok ne postane deljivo ja mislim...
@dpetek jel to konačno rješenje
jer ja to rješavam već neko vrijeme i cijelo vrijeme mi ispšisuje 0
Nije bas ... Formula je dobra, ali tu je modulo aritmetika koja malo zeza ... Kasnije cu se malo poigrati s tim, pa javim jel ovaj pristup vodi k prihvatljivom rjesenju ,,,
