C++ uzdevums "Vieninieki"

[Dunks]

Uzdevums

 

Naturāla skaitļa a pieraksts skaitīšanas sistēmā ar bāzi p sastāv no n pēc kārtas sekojošiem vieniniekiem. Uzrakstiet programmu, kas ievadītām p un n vērtībām nosaka, kādas ir lielākās skaitļu 2 un 3 pakāpes ar kurām skaitlis a dalās bez atlikuma.

 

IevaddatiTeksta failā vienin.in dotas divu naturālu skaitļu p (1 < p < 10⁹) un n (n < 10⁹) vērtības.

 

IzvaddatiTeksta failā vienin.out jāizvada divi veseli nenegatīvi skaitļi: lielākās divnieku un lielākās trijnieku pakāpes kāpinātāju vērtības.

 

Piemērsvienin.invienin.outPiezīmes17 21 2a=11₁₇=18₁₀Lielākās divnieka un trijnieka pakāpes ar ko šis skaitlis dalās ir 2 (2¹) un 9 (3²)10 40 0

 

 

 

http://www.lio.lv/ol...umi.php?show=20

 

(tas nav mājas darbs, ja kāds par to...), vienkārši man tādas hobijs - C++ uzdevumus risināt, bet jūtu, ka šis ir virs manas iesācēja galvas, tāpēc gribētos redzēt, kā Lieli vīri "dara lietas".

Pats esmu ticis tiktāl, ka ar nelieliem skaitļiem long long jeb __int64 viss ir pareizi, bet šeit nepieciešams operēt ar skaitļiem kuru kārta var sasniegt 10⁸¹

^{Lūk mans kods (Borland C++ Builder):}

 

#include <fstream>
#include <math>
#pragma hdrstop
#pragma argsused
using namespace std;
int main(int argc, char* argv[])
{

       unsigned long long temp(3),i3(0),i2(0),p,n,a=0;


       ifstream input;
       ofstream output;
     input.open("vienin.in");
     input>>p>>n;
  	input.close();

       for(;n--;a+=pow(p,n)); // izrēķinam pašu skaitli a

       while(0==a%temp)
  	{
  			temp*=3;
               ++i3;
  	}
  	temp=2
       while(0==a%temp)
       {
  			temp*=2;
  			++i2;
  	}
  	output.open("vienin.out");
  	output<<i2<<" "<<i3;
output.close();
return 0;
}

Labots Augusts 2, 2011 - Dunks

[učuks]

Ja darīšanas ar tik lieliem skaitļiem, tad jāizmanto paša veidots mainīgais. Viena, ne tā labākā metode, ir char masīvu (cik vien vajadzīgs garu, piem. 82 baiti) izmantot, lai katrā viņa elementā glabātu attiecīgu dotā skaitļa kārtas vērtību: 0-tajā vieniniekus, 1-jā desmitniekus u.t.t. Funkcijas, kuras veic elementārās matemātiskās darbības ar šādiem mainīgajiem, jāuzraksta pašam. Treniņa nolūkā var izpildīt uzdevumu: teksta faila divās rindās doti 2 skaitļi decimālajā pierakstā. Neviens no viņiem nav garāks par 200 zīmēm. Uzrakstīt programmu, kura nolasa šos skaitļus un rezultāta faila četrās rindās izvada attiecīgi pirmā un otrā skaitļa summu, starpību, reizinājumu un dalījumu.

[0xDEAD BEEF]

Tur ir pilnigi skaidrs, ka pieeja, ar kuru tu so skaitli parvert par "skaitli" un tad megini dalit ir garam!

Sis laikam ir vairak matematikas uzdevums.

skaitlis a = p^1 + p^2 + p^3 .... + p^n = p (1 + p^1 .. p^n-1) = p ( 1 + p (1 + p^1 ... p^n-2) = .... p(1 + p(1 + p ...... p(1 + p))))...)

Reikinat pasu skaitli ir absoluti bezjedzigi. Nepietiek resursu. uzdevumam noteikti jaieklaujas paris sekundes.

 

pec augseja pieraksta mes jau redzam dalu atbildes. Proti - vispirms izrekinam 2 un 3 augstakas pakapes pasam p. Talak, kad p ar kaut ko reizina, 2 un 3 pakapes palielinas par tik, pa cik otraja reizinataja ir augstakas pakapes.

Piemeram -

p = 9; 11 -> 9 + 9^2 -> 9(1 + 9)

9 -> 3^2; 9 * (1 + 9) = 2 trinieki no 9 + cik trijnieki ir (1 + 9) -> 0 = 3^2. nu un attiecigi ta vajag darit ar 2.

Tagad ir trikcy part - ko darit ar iekavam.

proti kada ir 2^ un 3^ pakape sadam jokam (1 + p(whatever)).

 

Es domaju, ka tas jasketina no otra gala. Proti - izrekini 2 un 3 pakapes 1 + p. Atceries, ka reizinot, vienmer max pakapes summejas. Kvadrat iekavas liksu zinamas pakapes. rezultata jaiegust tirs reizinajums.

piemeram - n = 4, p(1 + p(1 + p(1 + p)))) -> [p](1 + p(1 + p[1+p]))) -> [p](1 + p(1+[p[1+p]])

super tricky part -> 1+[p[1+p]] - te naks talka magija. ja skaitlis dalas ar 2, tad + 1 - nedalas ar 2. proti 2 pakapes klust par 0. ja skaitlis dalas ar 3, tad +1 vairs nedalas ar 3 un 3 pakapes klust par 0.

tadejadi mes jau zinam 1 + [p[1+p]] rezultatu (cik ir 2^x un 3^x). Ta mes skitinam sito visu valja un rezultats roka.

 

edit: aa lol fcuk! a ko darit, ja skaitlis nedalas ar 2 un tam pieskaita 1? esmu izgazies

Beefs

Labots Augusts 2, 2011 - 0xDEAD BEEF

[Dawis]

Nu tas pēc būtības ir matemātisks uzdevums..

Man šķiet ka vislabākais ir:

1. konvertēt šo skaitli vispirms uz bināro sistēmu - pārbaudīt lielāko divnieka pakāpi ar kuru dalās

2. Konvertēt šo skaitli uz trenāro(trijnieku) sistēmu - pārbaudīt lielāko trijnieka pakāpi ar kuru dalās.

 

Ja skaitlis ir attiecīgajā sistēmā tad ir ļoti viegli pārbaudīt kāda ir lielākā sistēmas bāzes pakāpe ar kuru skaitlis dalās..

Piemērs decimālā sistēma:

Ir taču viegli pateikt kāda ir lielākā 10nieka pakāpe ar kuru jebkurš skaitlis decimālajā sistēmā dalās:

Atbilde: Paskatamies cik nulles skaitlim ir beigās un tāda arī ir lielākā 10nieka pakāpe ar kuru dalās bez atlikuma.

 

Piemēram 347347100 dalās ar 100 jeb 10^2..

 

Tas pats izpildās 3niekiem trenārajā un 2vniekiem binārajā sistēmā..

 

Piemēram skaitlis 1010111100101010100000 binārajā sistēmā dalās ar 100000 bez atlikuma, kas ir 2 ^ 5 jeb 32..

 

Attiecīgi sanāk ka vienīgais sarežģītais te ir konvērtēt skaitli no vienas sistēmas uz otru ir, varbūt piņķerīgs, bet diezgan viegls uzdevums.. Ja piņkerējas doma paskaties wikipēdijā algoritmu.

Labots Augusts 2, 2011 - Dawis

[0xDEAD BEEF]

nu padoma dawis, tam skaitlim var but baze viens miljons un ciparu skaits viens miljons. Ja tu dasu konvertetu uz binaro sistemu - tas butu skaitlis ar bezgaligi daudz cipariem. kompis to nepavilktu.

Beefs

 

 

[Dawis]

nu padoma dawis, tam skaitlim var but baze viens miljons un ciparu skaits viens miljons. Ja tu dasu konvertetu uz binaro sistemu - tas butu skaitlis ar bezgaligi daudz cipariem. kompis to nepavilktu.

Beefs

konverteshanu var izdarit pa vienam ciparam vienlaicigi.. tam nav nepiecieshams njemt un visu skaitli uzreiz konvertet, kas protams nebūtu iespējams. bet pa vienam ciparam to izdarīt ir salīdzinoši vienkārši.

to skaitli vr uztvert ka ciparu virkni..

 

Bet padomājot vēl man viss liekas pat vēl elementārāk..

 

Paņemam skaitļa pēdējo ciparu , kas vienmēr būs kaut kāds skaitlis pirmajā pakāpē..

Izdalām ar 3.. viegla darbība.

Nākamā cipara vērtība ir iepriekšējais skailis kvadrātā..

Pēc matemātikas likumiem sanāk ka var vienkārši sareizināt atlikumus un iegut jauno atlikumu..

elementāri..

 

Piemēram pieņemsim ka sistēma ir 121265 un skaitlis ir 111111111.

 

Paņemam pēdējo ciparu kura vērtība ir 121265 izdalām ar 3 atlikumā dabujam 2 (starp citu ja dalītos šis cipars tad ari nākamo ciparu vērtības dalās ar 3 un viss skaitlis dalās ar 3)

Nākāmā cipar vērtība ir 121265 ^ 2 bet atlikums dalot ar 3 būs vienkārši 2 * 2 mod 3 = 1.

Nākamā cipara vērtība ir 121265 ^ 3 bet atlikums dalot ar 3 būs vienkārši 2 * 2 * 2 mod 3 = 0.

utt..

Saŗeķinam kopā visus atlikumus no ciparu vērtībām un izdalam ar 3 ja dalās ar 3 tad viss skaitlis dalās ar 3 ja ne tad ne..

 

Ja skaitlis nedalās ar 3 tad atbilde uz jautājumu ir 0, ja dalās tad vismaz 1.

Tāpēc turpinām - noskaidrosim vai skaitlis dalās ar 9.

t.i. šoreiz ar 3 pirmā cipara vērtība jādala ar 9.

Ja dalās tad ejam tālāk utt..

 

Reducējot:

 

Paņemam skaitļa sistēmu p un izdalām ar 3.

Pēc tam paņemam ciparu skaitu n

Mums pirmajā solī jāizrēķina:

((p mod 3) ^ n )mod 3 = ?

 

Ja iznākums ir 0 tad dalās ar 3 un ejam tālāk algoritms ir šāds

 

const = 3.

sk = const.

i = 0.

while (((p mod 3) ^ n )mod 3 == 0)

{

i++;

sk = sk*const.

}

 

cout <<"Maksimālā 3nieka pakāpe ar kuru dalās ir "<<i<<endl;

 

 

const = 2.

sk = const.

i = 0.

while (((p mod 3) ^ n )mod 3 == 0)

{

i++;

sk = sk*const.

}

 

cout <<"Maksimālā 2nieka pakāpe ar kuru dalās ir "<<i<<endl;

 

Piebilde:

 

Protams tas ir pseidokods un tā kā ciparu skaits ir miljons tad implementējot tieši tā kā rakstīts var būt problēmas ar to daļu kur jākāpina pakāpē n.

Bet atcerēsimies ka darbojamies ar skaitļiem 2 un 3.

Vienā gadījumā atlikumi var būt 0 un 1.

Otrā 0, 1 un 2.

Ar 0 un 1 problēmas nekad neradīsies - tas ir triviāli.

 

Ar atlikumu 2 arī problēmām nevajadzētu rasties. Trulas kāpināšanas vietā varam vienkārši saprast ka neviena 2nieka pakāpe ar 3 nekad nedalīsies un atlikumi vienmēr būs cikliski:

 

2 ^ 0 mod 3 = 1

2 ^ 1 mod 3 = 2

2 ^ 2 mod 3 = 1

2 ^ 3 mod 3 = 2

utt.

Vispārīgi runājot pāra pakāpes dod atlikumā 1 un nepāra pakāpes 2.

Labots Augusts 2, 2011 - Dawis

[0xDEAD BEEF]

Tu smagi nomudijies manuprat!

Panem to pasu savu bazes sistemu un izrekini tada gadijuma pierakstu 3nieku sistema skaitlim 111 (121265 ). imho ir mazliet sarezgitak!

Beefs

[Vilx-]

Ja p un n vērtības ir 10⁹, tad decimālajā pierakstā tam skaitlim ir 10¹⁸ ciparu. Lai arī kā Tu to mēģinātu pārveidot par skaitli binārā vai trinārā pierakstā (man vienalga, vai pa daļām vai visu reizē), Tu ātrāk nosirmotu nekā sagaidītu procesa beigas.

 

Nē, šeit pilnīgi noteikti jāmeklē matemātisks risinājums, un programmēšana šeit būs otršķirīga.

 

Ē, gadījumā ar 2 atbilde ir redzama no BEEF'a pieraksta:

p(1 + p(1 + p ...... p(1 + p))))...)

 

Domājam no otra gala - pieņemsim, ka p dalās ar 2ⁿ. Tātad, tas ir pāra skaitlis. 1+p ir nepāra skaitlis, kas nozīmē, ka tas vispār nedalās ar 2. p(1+p) tātad atkal dalās tikai ar 2ⁿ. Bet 1+p(1+p) atkal jau ir nepāra. U.t.t. Secinājums - viss skaitlis dalīsies tikai ar 2ⁿ. Tagad tikai noskaidrot, kāda ir lielākā 2 pakāpe, ar kuru dalās p. To laikam visvienkāršāk programmātiski izdarīt, skatoties, cik biti ir 0 labajā pusē. Ķipa:

int GetLog2(uint x)
{
   if ( x == 0 )
      return 0; // Vai drīzāk exception
   int rezult = 0;
   while ( x )
   {
       if ( x & 1 )
           break;
       rezult++;
       x >>= 1;
   }
   return rezult;
}

 

Tagad jāpaskatās, kas ir 3 gadījumā.

Labots Augusts 2, 2011 - Vilx-

[Dawis]

Tu smagi nomudijies manuprat!

Panem to pasu savu bazes sistemu un izrekini tada gadijuma pierakstu 3nieku sistema skaitlim 111 (121265 ). imho ir mazliet sarezgitak!

Beefs

Jā atvaino ar konvertēšanu nesanāks - nepaskatījos ka bāze var būt līdz miljonam (domāju ka līdz 9), bet tas ko rasktīju zemāk ir viegli un izrēķināsies pāris mikrosekundēs.

 

(Zemāk esošajam kodam ir vismaz viens trūkums. Pie dotajiem parametriem viegli var sanākt ka lielākās 2nieku un 3nieku pakāpes ar kurām skaitlis dalās ir tik lielas ka tās nevar atspoguļot ne 32 ne 64 bitu integeros.. jāpameklē vēl kāda atlikumu īpašības kas balstās uz skaitļu pakāpēm)

Pseidokods:

//n  - number count or count of 1's
//p  - system base

const c3 int value 3;
const c2 int value 2

int num , rez, atl, sum_atl, atl_tmp.


num = c3.

i = 0;
while (1 = 1)                                               // Šis cikls skaita pakāpec cik tālu esam tikuši.. mēs apstājamies pie pirmās 2nieka vai 3nieka pakāpes kas nedalās.
{
    num = c3;
 rez = p;
 atl = 0;
 for( int t = 0 t <= i; t++)                        // Šī cikla vienīgais uzdevums ir noskaidrot kādu atlikumu veido p dalot ar konkrēto divnieka vai 3nieka pakāpi.
 {                                                  // To var izdarīt vienkāršāk taču centos izadarīt visu pēc iespējas vienkāršāk tā lai izvairītos no overlfow
	 rez = rez / num.                           // var ari protams vienkārši aizstāt ar atl = p mod ( num ^ (i+1)).
	 atl_tmp = rez mod num.
	 atl = atl_tmp * num ^ t + atl.
 }
 sum_atl = 0;
 for (int i = 1; i <= n; i++)                       // Šī cikla galvenais uzdevums ir noskaidrot kāds atlikums veidosies dalot doto skaitli ar konkrēto 2nieka vai 3nieka pakāpi
 {
	sum_atl += atl.
	atl = ((atl * atl) mod num ^ (i+1));
 }
 sum_atl += atl;
 if(sum_atl mod num ^ (i+1) == 0)
 {
	i++;
 }
 else
 {
	break;
 }
}
cout<<"Dotais Skaitlis bez atlikuma dalās ar "<<num<<" pakāpē "<<i<<endl;

 

Tīri matemātiski viss atrisinājums balstās uz moduļu jeb atlikumu īpašībām. To ir daudz un tās var vērtīgi izmantot un pārsvarā tās ir arī viegli saprast:

http://en.wikipedia.org/wiki/Modular_arithmetic

http://en.wikipedia.org/wiki/Modulo_operation

 

Tik specifiskā gadījumā kā šis kad darbojamies vien ar 2 vai 3 noteikti pat varam izdomāt ko vēl vienkāršāku.

Labots Augusts 2, 2011 - Dawis

[0xDEAD BEEF]

Vilks - nezinu, vai ir tik vienkarsi taja mana pieraksta.

Jaa - viena mirkli - opaa - nedalas. Nais. Bet nakamaja mirkli to skailti pareizina un pieskaita 1. un tagad atkal dalas. Un ka lai zin, ar cik dalas. Tb - skaidrs, ka dalas ar 2, bet ar kuru augstako 2^ dala, tas vairs nav skaidrs.

Es saku meginat uz papira izteikt to p forma 2^a + 3^b + c, bet ari ta tur nekas jedzigs nesanak (so far).

 

Proti - problema ir sekojosa - ja mes ejam no beigam taja 1+p (... pieraksta, tad mes viegli tiekam gala ar p*(p+1), bet ko darit talak - pec +1.

Beefs

Labots Augusts 2, 2011 - 0xDEAD BEEF

[Dawis]

Vilks - nezinu, vai ir tik vienkarsi taja mana pieraksta.

Jaa - viena mirkli - opaa - nedalas. Nais. Bet nakamaja mirkli to skailti pareizina un pieskaita 1. un tagad atkal dalas. Un ka lai zin, ar cik dalas. Tb - skaidrs, ka dalas ar 2, bet ar kuru augstako 2^ dala, tas vairs nav skaidrs.

Es saku meginat uz papira izteikt to p forma 2^a + 3^b + c, bet ari ta tur nekas jedzigs nesanak (so far).

 

Proti - problema ir sekojosa - ja mes ejam no beigam taja 1+p (... pieraksta, tad mes viegli tiekam gala ar p*(p+1), bet ko darit talak - pec +1.

Beefs

Ņemot vērā ka ir olimpiādes uzņēmums ir vai nu jākoncentrējas tiešu uz skaitļu 2 un 3 īpašībām vai jāizmanto kāda no jaukajām skaitļu teorijas piemirstajām teorēmām.

Pašlaik acis metu uz Eilera jeb Fermā mazo teorēmu.

[Dunks]

 

 

Paņemam skaitļa pēdējo ciparu , kas vienmēr būs kaut kāds skaitlis pirmajā pakāpē..

 

nevis pirmajā, bet nulltajā. t.i. vieninieks jebkurā sistēmā, piem. binārajā sistēmā 111 = 1x2² + 1x2¹ + 1x2⁰ = 4 + 2 + 1 = 7

[Dawis]

nevis pirmajā, bet nulltajā. t.i. vieninieks jebkurā sistēmā, piem. binārajā sistēmā 111 = 1x2² + 1x2¹ + 1x2⁰ = 4 + 2 + 1 = 7

Jā zinu, tur man kļūda ir bet tas vieninieks tur daudz neizšķir.. algoritms darbojas tikuntā..vienīgā problēma pašlaik ir milzīgas 3nieku pakāpes, pie kurām ir nereāli sastādīt atlikumu sistēmas.

Es vēl paskatīšos va nevar kaut ko nooptimizēt.

Labots Augusts 2, 2011 - Dawis

[Dunks]

for (int i = 1; i <= n; i++) // Šī cikla galvenais uzdevums ir noskaidrot kāds atlikums veidosies dalot doto skaitli ar konkrēto 2nieka vai 3nieka pakāpi

{

sum_atl += atl.

atl = ((atl * atl) mod num ^ (i+1));

}

sum_atl += atl;

if(sum_atl mod num ^ (i+1) = 0)

{

i++;

}

[/code]

Vai pareizi saprotu, ka simbols ^ šeit nozīmē bitwise XOR pēc C++?

Un vai citātā pēdējā if-ā ...if(sum_atl mod num ^ (i+1) = 0)... = simbols domāts kā pieškiršanas operators?

 

 

[0xDEAD BEEF]

Tas ir domat pacelt pakape!

Beefs

 

Heh!

 

Es tā sāku štukot - n = 6, p = 2.

111111 = 63 = 3^2 * 7

 

Es nezinu, kā pie šitās vērtības (9) var tikt, neizmantojot p^n vai 3^p.. točna nezinu... domāju, ja šito var izdomāt, tad jau easy!

 

Beefs

[Dawis]

1. domāts kā power jeb kāināšana

2. domāta salidzinašana..

 

Atvainojos par pseidokoda kvalitāti - nav pat c++ kompilatora:)

 

Es tagad domāju kā to varētu tik tālu vienkāršot, ka nebūtu pat jāizmanto atlikumu , jeb moduļu reizināšana..

 

Interesanti ka:

1. ) Uzdevums būtu pavisam vienkāršs ja mēs runātu par skaitļiem formā 111111110, jo tad mēs runātu par bāzes p daudzkārtni - pietiktu p izdalīt ar 2 vai 3 un tālāk vigli varētu izrēķināt cik reizes 2 vai 3 ieet skaitlī kas ir formā 11111110.

 

P.S.

algoritms ko ieliku faktiski strādā ļoti labi ja pieņemam, ka 2 vai 3 pakāpe, ar kuru dalās skaitlis a būtiski nepārsniedz log3(p) vai log2(p). Bet mani, tomēr, neliek mieru vai neeksistē slimi gadījumi, kad 2nieka vai 3nieka pakāpe ar kuru dalās skaitlis a ir milzonīgi liela. Katrā ziņā ja šādi gadījumi ir tiem jābūt ļoti retiem, tāpēc pieņemu, ka mans risinājums faktiski ir pieņemams (es gan pieļauju ka ātrumā rakstot būšu ko sarakstījis nepareizi un tāpēc rītdien varbūt publicēšu tīrāku versiju)..

Labots Augusts 2, 2011 - Dawis

[0xDEAD BEEF]

Klau dawis, sorry par tupumu, bet tu lūdzu varētu paskaidrot savu algoritmu uz tik tupu piemēru kā 111111(2)?

Beefs

[Dawis]

Klau dawis, sorry par tupumu, bet tu lūdzu varētu paskaidrot savu algoritmu uz tik tupu piemēru kā 111111(2)?

Beefs

 

Nu tas ko uzrakstīju noteikti nebija viegli saprotams, jo rakstīju steigā un izteicos neskaidri..

 

Tātad pieņemsim ka cenšamies noskaidrot ar kādu 3 pakāpi dalās 111111.

p = 2.

 

Pirmā ir pārbaude vai skaitlis dalās ar 3^1 jeb 2.

 

Kā jau tu teici skaitli var izteikt formā p^0 + p^1 + p^2 + ..

Tātad lai noskaidrotu atlikumu kas būtu ja visu skaitli dalītu ar 3 mēs varam šādi:

(p^0 mod 3 + p^1 mod 3 + p^2 mod 3 + ..) mod 3, kas protams ir triviāli, un liekas sarežģīti taču dēļ atlikumu īpašībām ir vienkārši.

 

Šajā piemērā:

Pēdējais cipars vienmēr dod atlikumu 1.

Otrais (no beigām) cipars dos atlikumā p mod 3 = 2 mod 3 = 2.

 

Trešais cipars dos atlikumā (p^2 mod 3) = 4 mod 3 = 1.

Taču to var aprēķināt arī kā p^2 mod 3 = (p * p mod 3) mod 3 = (p mod 3 * p mod 3 ) mod 3 = 2 * 2 mod 3 = 1 (atšķirību var saprast ja iedomājas ka p = 123235 nevis 2)

 

Ceturtais cipars atlikumā dos (p mod 3 * p mod 3 * p mod 3) mod 3 = 1 * 2 mod 3 = 2.

 

Piektais: 2 * 2 mod 3 = 1.

 

Sestais: 2. (Pārbaude: Sestā cipara no beigām jeb pirmā no sākuma vērtība ir 100000 jeb 32, kas tiešām dod 2 atlikumā dalot ar 3)

 

Tātad kopējais atlikums dalot ar 3 ir = (1 + 2 + 1 +2 +1 + 2) mod 3 = 0

 

Citiem vārdiem sakot skaitlis dalās ar 3.

Tagad mums jāpārbauda vai skaitlis dalās ar 3^2 jeb 9.

 

To var darīt tā ka vienkārši paņem p mod 9 = 2 mod 9 = 2.

Vai arī izmantojot iepriekšējos rezultātus:

Tā kā p div 3 = 2 div 3 = 0 atlikumā 2.

Tad p div 9 = 0 (iepriekšējais dalījums) mod 3 * 3 + 2 {Šaja gadījumā grūti saprast, bet Piemēram: 17 mod 9 = 8. Bet to var aprēķināt arī šādi: 17 div 3 = 5 atlikumā 2 tāpēc 17 mod 9 = (5 mod 3) * 3 + 2 = 6 + 2 = 8 }

 

Esam ieguvuši sākuma atlikumu 2.

Tagad to tāpat kā iepriekš sarēķinam katram ciparam:

pirmam no beigām = 1.

Otrajam = 2.

Trešajam = 4. ((2 * 2) mod 9)

Ceturtajam = 8. ((4 * 2) mod 9)

Piektajam = 7. ((8 * 2) mod 9)

Sestajam = 5. ((7 * 2) mod 9)

 

Saskaitot kopā (1 + 2 + 4 + 8 + 7 + 5) mod 9 = 27 mod 9 = 0 jeb dalās ar 3^2 jeb 9.

 

ejam tālāk.

 

p mod 27 = 2.

 

Pirmajam ciparam no beigām = 1

Otrajam = 2

Trešajam = 4

Ceturtajam = 8

Piektajam = 16

Sestajam = 5 (16 * 2 mod 27)

 

Kopā saskaitot (1 + 2 + 4+ 8 + 16 + 5) mod 27 = 9 (nedalās)

 

Tātad maksimāla 3 pakāpe ar kuru dalās ir 2 jeb skaitlis 9.

[kogi]

Dazas idejas:

1.apskatit pec kartas kadas 10 p un n vertibas. Varb'ut rezultatos ir pamanamas kadas sakaribas.

2. aplukojam p , kas ir parskaitlis , teiksim 2k, tad a= (2k^n-1)/(2k-1), kas ar 2 nedalas (vai te nav kludas redzams no punkta 1)

3. aplukojam p , kas ie nepaskaitlis , teiksim 2k+1, , tad manuprat var nonakt pie atzinas ka a, dalas ar to pasu 2 pakapi, ar kadu dalas 2n.

[Dawis]

Atradu online c++ emulātoru, kurā es ieliku savu algoritmu:

http://codepad.org/sLZnE5Sz

 

BTW: Ļoti noderīga štelle..

Diemžēl neizdevās uztaisīt programmu ar parametriem, bet kas grib tur uzvietas var paspēlēties ar ieejas konstantēm.

Izaicinu atrast pieļaujāmās p un n vērtības pie kurām programma nenostrādā..

 

Drošības pēc ielikšu kodu arī te:

int main()
{


int num;
int atl, sum_atl, atl_next;

int n = 60;
int p = 2;
num = 3;

int power = 0;
while (1)              
{
        atl = p%num;
        cout<<"p mod num = "<<atl<<endl;            
        sum_atl = 1;
        atl_next = atl;
        for (int t = 1; t < n; t++)                       // Šī cikla galvenais uzdevums ir noskaidrot kāds atlikums veidosies dalot doto skaitli ar konkrēto 2nieka vai 3nieka pakāpi
        {
               cout<<n-t<<". cipara dotais atlikums = "<<atl_next<<endl;
               sum_atl += atl_next;
               atl_next = (atl_next * atl) % num;
        }      
        cout<<"Kopējais atlikums = "<<sum_atl<<endl;
        if(sum_atl % num == 0)
        {
               power++;
               cout<<"dalās ar "<<num<<endl; 
               num *= 3;
        }
        else
        {
               break;
        }
}
cout<<"Dotais Skaitlis bez atlikuma dalās ar "<<3<<" pakāpē "<<power<<endl;

return 0;
}

 

Dazas idejas:

1.apskatit pec kartas kadas 10 p un n vertibas. Varb'ut rezultatos ir pamanamas kadas sakaribas.

2. aplukojam p , kas ir parskaitlis , teiksim 2k, tad a= (2k^n-1)/(2k-1), kas ar 2 nedalas (vai te nav kludas redzams no punkta 1)

3. aplukojam p , kas ie nepaskaitlis , teiksim 2k+1, , tad manuprat var nonakt pie atzinas ka a, dalas ar to pasu 2 pakapi, ar kadu dalas 2n.

Nu es šodien izrakos cauri tādai izkožamajai skaitļu teorijai (pieņemu ka kaut kas elitārs un grūti atrodams šeit nav izmantojams...)

Jā kā jau var pamanīt no programmas rezultātiem 2nieku un 3nieku pakāpju atlikumu kopas veido cikliskas grupas un vēl visādus interesantus veidojumus, tā ka visumā sakarības var atrast ļoti daudz.

Bet tādu vienkāršu veidu kā teiksim uzreiz predzēt atlikumu summas vai to vai dalīsies neanalizējot katru ciparu un pakāpi atsevišķi es tomēr nevarēju..

 

Bet daudzas interesantas sakarības var atrast gan..

[Dunks]

Ja p un n vērtības ir 10⁹, tad decimālajā pierakstā tam skaitlim ir 10¹⁸ ciparu.

 

Vispār jau, ja bāze ir rupji runājot miljards, tad 18 ciparu skaitli decimālajā sistēmā mēs dabūsim jau ar skaitli 111 pie bāzes miljards

 

111_{p=999 999 999}=1*999 999 999^2 + 1*999 999 999^1 + 1*999 999 999^0 = 999 999 998 000 000 001 + 999 999 999 + 1 = 999 999 999 000 000 001

 

Ja netici ieraksti Googles lodziņā (kurā starp citu ir iebūvēts kalkulators) 999 999 999^2, un rezultātā iegūsi

= 9.99999998 × 10¹⁷

^{Tā ka ciparu tur būs maķenīt vairāk, interesanti cik?}

Labots Augusts 3, 2011 - Dunks

[Dawis]

Vispār jau, ja bāze ir rupji runājot miljards, tad 18 ciparu skaitli decimālajā sistēmā mēs dabūsim jau ar skaitli 111 pie bāzes miljards

 

111_{p=999 999 999}=1*999 999 999^2 + 1*999 999 999^1 + 1*999 999 999^0 = 999 999 998 000 000 001 + 999 999 999 + 1 = 999 999 999 000 000 001

 

Ja netici ieraksti Googles lodziņā (kurā starp citu ir iebūvēts kalkulators) 999 999 999^2, un rezultātā iegūsi

= 9.99999998 × 10¹⁷

^{Tā ka ciparu tur būs maķenīt vairāk, interesanti cik?}

 

9.99999998 × 10^17 ir ļoti tuvu 10 ^ 18

Labots Augusts 3, 2011 - Dawis

[0xDEAD BEEF]

Ja, bet tas bija 18 ciparu skaitlim, pie bazes miljards! cik bus miljards ciparu skaitlim pie bazes miljards? loti vienkarsi - miljards^miljards. loti loti daudz!

Vispar paldies, tagad tavs algoritms skaidrs (protams, saubos, ka stradas uz tiem lielajiem skaitliem). Nav slikts. Nezinaju mod matematiku.

Beefs

[Dunks]

9.99999998 × 10^17 ir ļoti tuvu 10 ^ 18

 

Jautājums bija par to, ar cik cipariem decimālajā sistēmā rakstīsies skaitlis, kas atbildīs uzdevuma maximālajiem nosacījumiem.

 

Lūk pats maksimālais skaitlis:

 

1*999 999 999^{999 999 998} + 1*999 999 999^{999 999 997}+ 1*999 999 999^{999 999 996} + ... ... + 1*999 999 999¹ + 1*999 999 999⁰

Rupji runājot , ja

 

1 000 000 000^10 = 1.0 × 10^90,

^tad

1 000 000 000^1 000 000 000 = 1.0 × 10^{9 000 000 000},

tātad maximālais skaitlis decimalajā sistēmā rakstīsies ar 9 miljardiem ciparu, jeb 9 x 10⁹ ciparu.

Labots Augusts 4, 2011 - Dunks

[Dawis]

Vispar paldies, tagad tavs algoritms skaidrs (protams, saubos, ka stradas uz tiem lielajiem skaitliem). Nav slikts. Nezinaju mod matematiku.

Beefs

Uz lielajiem skaitļiem strādās pilnīgi noteikti.. Vienīgā prasība, ka 3nieka/2nieka pakāpes ar kurām dalās dotais skaitlis nevar augt neierobežoti.

Teiksim kāda 10 - 15 pakāpe mierīgi.

Atrast tādus skaitļus kas dalās ar 3^30 un 2^40 ir diezgan pagrūti.

Cik es pētiju man sāka likties ka skaitļi formā 111111...111 ir specifiski jebkurā skaitīšanas sistēmā un vispār runājot ir diezgan reti.. Gan jau, protams, kāds no tiem ir kādas lielas 2nieka vai 3nieka pakāpes daudzkārtnis.

 

Ja abi ievades parametri ir ierobežoti 10^9 tad vispār ir 10^18 iespējamo ievades kombināciju.

 

Par to ka šie skaitļi ir reti var pārliecināties kaut vai tāpēc, ka iespējamo ievades kombināciju (skaitļu) ir "tikai" 10^18 bet maksimālais skaitlis, kuru var aprakstīt ar šīm ievades kombinācijām ir 10 ^ (10 ^ 18) . Tātad tikai 10^18 skaitļi ir izkaisīti intervālā 0 ... 10 ^ (10 ^18).. Tas ir kā daži atomi galaktikā..

Zinot ka arī lielo divnieka un trijnieka pakāpju daudzkārtņi nav bieži sastopami varam noskārst ka ļoti ļoti ļoti reti vajadzētu būt gadījumiem, kad kāds no šiem skaitļiem dalās ar lielu 2nieka vai 3nieka pakāpi..

 

Protams, kas uz šī fona ir liela pakāpe.. Bet vispār runājot ar 64 bitu integeru varam mierīgi aprakstīt 2^64 atlikumu sistēmu jeb 3^40, kas es uzskatu ir pilnībā pietiekami.

Pietiekami tāpēc, ka ar 2^64 vai 3^40 dalās vidēji viens skaitlis no 10^19 skaitļiem, un ņemot vērā ka vispār ar ievades datiem varam aprakstīt 10^18 ļoti specifiskus skaitļus, domāju ka mums ir visai labas cerības netrāpīt uz kāda kas dalās teiksim ar 3^70 vai 2^102.

 

Mans secinājums ir tāds, ka pie dotajiem ievades ierobežojumiem algoritmam vajadzētu darboties ātru un uzticami, turklāt vēl ir atstāta telpa uzlabojumiem, lai gan tur jebkurā gadījumā ir aditīvs cikls cauri maksimums 10^9 cipariem (izpildīsies ātri) un ārējais cikls nekad neizpildīsies vairāk kā 40 reizes (parasti 1 vai divas)..

 

Iespējamais uzlabojums ir tāds, ka tiklīdz mēs kārtējā iterācijā dabūjam atlikumu kas ir jau dabūts kādā no iepriekšējām iterācijām mēs uzreiz secinam ka ir iestājies cikls un vairs neciklējamies cauri visiem cipariem, bet vienkārši aritmētiski izrēķinām kādām ir jābūt beigu atlikumam.. Tas limitēs iekšējā cikla iterāciju skaitu uz kādām vidēji 10 - 20 iterācijām(maksimums gan var strauji augt ja sanāk ka skaitlis dalās ar milzīgu divnieka vai trijnieka pakāpi), kas algoritmam ļaus darboties vienkārši zibenīgi..

 

 

Jautājums bija par to, ar cik cipariem decimālajā sistēmā rakstīsies skaitlis, kas atbildīs uzdevuma maximālajiem nosacījumiem.

Tur jau arī gāja runa par 10^18 ciparu nevis par 10^18 kā tādu..

Skaitlis ar 10^18 cipariem decimālakā sistēmā maksimāli apraksta vērtību 10^(10^18) - 1. (9999999......9999999 (10^18 reizes))

Labots Augusts 3, 2011 - Dawis

[0xDEAD BEEF]

Es izdomaju vienu skaitli, kurs dalas ar 3^16, bet tas ir divciparu skaitlis!

int n = 2;

int p = 43046720;

 

Skiet, ka ciparu skaitam palielinots, 3^ maksimala pakape loti strauji samazinas (lidz 3).

Interesanti, kas to nosaka. Kadelj atlikumu summas negrib veidoties tadas (bez 1ninieka), lai summa sanaktu 2, 8, 26, 80, 242, etc.. :/

Beefs

[Dawis]

Es izdomaju vienu skaitli, kurs dalas ar 3^16, bet tas ir divciparu skaitlis!

int n = 2;

int p = 43046720;

 

Skiet, ka ciparu skaitam palielinots, 3^ maksimala pakape loti strauji samazinas (lidz 3).

Interesanti, kas to nosaka. Kadelj atlikumu summas negrib veidoties tadas (bez 1ninieka), lai summa sanaktu 2, 8, 26, 80, 242, etc.. :/

Beefs

Nu jā tādus divciparu un vienciparu skaitļus ir viegli izdomāt, paņem kādu trijnieka pakāpi un atņem 1 un to izvēlies par bāzi.

Viena no atbildēm uz tavu jautājumu varētu būt vienkārši tāda ka šie skaitli vienkārši ir statistiski reti, bet iespējams ir citi iemesli..

Teiksim jāpapēta kādi skaitļi ir lielu trijnieka pakāpju tuvumā un kā tie sadalās reizinātājos..

Kā jau teicu skaitļi formā 1111111 arī ir ļoti specifiski.. sastāvot no skaitļu p pakāpju summām..

Cik man zināms dažādu skaitļu pakāpes reti atrodas pārāk tuvu viena otrai..

Labots Augusts 3, 2011 - Dawis

[Dunks]

#include <fstream>
using namespace std;
typedef unsigned long long ul;
ul n, p;
void getPower(ul , ul*);
int main()
{
       ul power2(0), power3(0);
       ifstream& input = *new ifstream("vienin.in");
       input>>p>>n;
       input.close();
       delete& input;
if(1 != n)
{
 if(p%3)    //  Seit es atklaju sakaribu - ja skaitisanas sistemas baze bez atlikuma dalas ar num, tad lielakais num kapinatajs bus 0 ( power3(0) - inicializets jau sakuma)
   getPower(3, &power3);

 if(p%2)  // Seit ari taa pati sakariba
  getPower(2, &power2);
}
       ofstream& output = *new ofstream("vienin.out");
       output<<power2<<" "<<power3;
       output.close();
       delete& output;
       return 0;
}
//---------------------------------------------------------------------------
inline void getPower(ul num,  ul* power)
{
ul atl_next, atl, sum_atl, uniqueRemainders, loops, temp_atl, tempNum(num);

while (1)
 {
		sum_atl = temp_atl = atl_next = atl = p%num;
		uniqueRemainders = 1;
		while (temp_atl != (atl_next = (atl_next * atl) % num))
		{
  		++uniqueRemainders;
  		sum_atl += atl_next;
		}
		ul loops_atl = n%uniqueRemainders; // Atlikumu nepilnā "cikla" iterāciju skaits

		loops = n/uniqueRemainders;   // Atlikumu pilno "ciklu" skaits
		sum_atl *= loops;
		if (loops_atl)
		{
               atl_next = atl = p%num;
               sum_atl += atl_next;
               while(--loops_atl)
               {
        		atl_next = (atl_next * atl) % num;
        		sum_atl += atl_next;
               }
		}
		if( sum_atl % num ) break;
		else
		{
               *power += 1;
               num *= tempNum;
		}
 }

}

 

Šis kods olimpa uzdevumu pārbaudē iztur 9 testus no 10. 6. testā uzrāda kļūdu:

 

http://www.lio.lv/ol...?queue_id=43321

 

Tas nozīmē, ka kods nevis iedod nepareizu rezultātu, bet kaut kādu citu kļūdu (ieciklošanos vai overflow vai ko citu).

Varbūt kāds redz, kāda tieši ir kļūda?

Kļūdas kā tādas nav, Borlandā kods strādā ilgi (35-40sek), bet pareizi. Tas ir banāls taimauts.

Labots Augusts 11, 2011 - Dunks

[Dawis]

Tu neņem vērā pirmo atlikumu 1.

Dēļ tā ka atlikumu grupa ir cikliska, neskatoties uz to ka nesāc ar 1 cikla izmērs tiek noteikts pareizi (jo jebkurš grupas elements varētu tikt izmantots kā atbalsta punkts lai noteiktu cikla garumu), taču loop_atl vērtība tiek aprēķināta nepareizi.

 

 

Ieliku kodu šeit un pieliku klāt debug informāciju:

http://codepad.org/w47Atjso

 

Manuprāt no piemēra p = 2 n = 6 jau ir redzama kļūda.

Lai gan izdotais rezultāts ir pareizs, bet dēļ tā ka neņem vērā ka atlikums ir 1 nepareizi tiek izrēķināta nepilnā cikla summa jeb loop_atl.

 

Dotajā piemērā tā sanāk 45 taču tai būtu jānasnaķ 36. Faktiski mēs pārbaudām vai 63 dalās ar 27. 63 mod 27 = 9

Programma izrēķina atlikumu summu 45, bet 45 mod 27 = 18, kas nav rezultāts ko gribējām dabūt.

36 īstā atlikumu summa dod pareizu rezultātu 36 mod 27 = 9

Labots Augusts 7, 2011 - Dawis

[Dunks]

#include <fstream>
using namespace std;
typedef unsigned long long ul;
ul n, p;
void getPower(ul , ul*);
int main(int argc, char* argv[])
{
       ul power2(0), power3(0);
       ifstream& input = *new ifstream("vienin.in");
       input>>p>>n;
       input.close();
       delete& input;
if(1 != n)
{
	if(p%3)	getPower(3, &power3);

	if(p%2) getPower(2, &power2);
}
       ofstream output("vienin.out");
       output<<power2<<" "<<power3;
       output.close();       
       return 0;
}
//---------------------------------------------------------------------------
inline void getPower(ul num,  ul* power)
{
ul atl_next, atl, sum_atl, uniqueRemainders, loops, temp_atl, tempNum(num);

while (1)
 {
        sum_atl = temp_atl = atl_next = atl = p%num;
        //sum_atl = 1;
        uniqueRemainders = 1;
        while ((temp_atl != (atl_next = (atl_next * atl) % num)) && (uniqueRemainders < n))
        {
          ++uniqueRemainders;
          sum_atl += atl_next;
        }
	if (uniqueRemainders == n);
	else
	{
		ul loops_atl = n%uniqueRemainders;		
		loops = n/uniqueRemainders;   // Atlikumu pilno "ciklu" skaits
		sum_atl *= loops;
		if (loops_atl)
		{
				atl_next = atl = p%num;
				sum_atl += atl_next;
				while(--loops_atl)
				{
					atl_next = (atl_next * atl) % num;
					sum_atl += atl_next;
				}
		}
	}
        if( sum_atl % num ) break;
        else
        {
               *power += 1;
               num *= tempNum;
        }
 }

}

 

Kodu nedaudz palaboju, joprojām tā pati kļūda.

[Dawis]

Bet joprojām neredzu, ka tu ņemtu vērā atlikumu kas rodas no pirmā (pēdējā) cipara un vienmēr ir 1.

Ievietojot kodu turpat kur ieriekš un pieliekot klāt debug informāciju ir redzams, ka kodam ir tā pati problēma kas iepriekš:

http://codepad.org/fE0mbkmq

 

Papētot sīkāk šķiet, ka nonāku vēl pie pāris atziņām:

1. Kodā ir ausgstāk minētā kļūda, bet šķiet, ka tā nenoved pie kļūdaina rezultāta, jo (var jau būt ka tā ir sagadīšanās, bet) es nespēju atrast piemēru, kad kāds skaitlis dalītos ar kādu pakāpi ja cipru skaits nedalās ar atrastā cikla izmēru.. Respektīvi, ja loop_atl nav 0 nekad nedalās.

 

2. Kļūda visticāmāk saistīta ar overflow, kas rodas cikla atlikumam pārsniedzot tipu robežas.

Spēlējoties spēju uzģenerēt piemērus kas dalās ar iespaidīgām pakāpēm : http://codepad.org/9FnMH3Y1 un šķiet ka sakarība ir tāda ka, ka p = 3, tas jebkurš n , kas vienāds ar kādu 2nieka pakāpi dos 3 diezgan ievērojamu rezultātu 2nieku pakāpei ar kuru dalās.. Piedevām šķiet ka cikla izmērs vienmēr ir maksimālais un aug ļoti ātri, kas noved pie sum_atl overflow.

 

3. Ir gandrīz skaidrs ka cikla izmēru var noteikt iepriekš un tas saistīts ar eilera funkciju. Ja izdotos vēl pierādīt, ka tikai pilna cikla summa dalās ar nepieciešamo pakāpi bez atlikuma un daļējs cikls nekadneveidos atlikumu 0, tad mēs iegūtu vēl ar kārtu ātrāku algoritmu šīs problēmas risināšanai.

Labots Augusts 7, 2011 - Dawis

[Dunks]

3. Ir gandrīz skaidrs ka cikla izmēru var noteikt iepriekš un tas saistīts ar eilera funkciju. Ja izdotos vēl pierādīt, ka tikai pilna cikla summa dalās ar nepieciešamo pakāpi bez atlikuma un daļējs cikls nekadneveidos atlikumu 0, tad mēs iegūtu vēl ar kārtu ātrāku algoritmu šīs problēmas risināšanai.

 

Cikla izmērs = num ^{(power + 1)} - num^power

^{bet mūsu gadījuma tas neder, jo var pārsniegt mainīga tipa izmērus (jau izmēģināju)}

^piem.:

18 = 3³ - 3²

6 = 3²-3¹

 

Iespējams, ka tā kļūda 6. testā saistīta ar uzdevuma izpildes laiku max 1 sek. saskaņā ar uzdevuma nosacījumiem

[Dawis]

Cikla izmērs = num ^{(power + 1)} - num^power

^{bet mūsu gadījuma tas neder, jo var pārsniegt mainīga tipa izmērus (jau izmēģināju)}

^piem.:

Nevar būt..

Piemēram num = 3 power = 3. Pēc būtības meklējam ciklu atlikumu sistēmā 27 pie ģeneratora 2.

Pēc tavas formulas sanāk ka būtu jābūt 3 ^ 4 - 3 ^ 3 = 81 - 27 = 54 elementi.

Tas nav iespējams jo atlikumu sistēmas multiplikatīvā grupa sastāv no maksimums 27 - 1 = 26 elementiem.

Teorija: http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n saka , ka atlikumu sistēmām pēc 2^n pakāpēm būs grupas ar izmēru 2^(n-2) kā arī viena grupa ar diviem elementiem.

 

Bet atlikumu sistēmām a^n, kur a pirmskaitlis (kas atbilst 3nieka gadījumam) grupu izmērs ir Fi (a^n), kur Fi ir eilera funkcija un tas vienāds ar a^(n) - a^(n-1).

 

Redzu, ka tas nav tālu no tā kā rakstīji, un varbūt es vienkārši ne tā uztvēru, tomēr grupu (ciklu) izmēri 2nieku un 3nieku gadījumā atšķirās..

Labots Augusts 7, 2011 - Dawis

[Dunks]

Bet atlikumu sistēmām a^n, kur a pirmskaitlis (kas atbilst 3nieka gadījumam) grupu izmērs ir Fi (a^n), kur Fi ir eilera funkcija un tas vienāds ar a^(n) - a^(n-1).

 

Redzu, ka tas nav tālu no tā kā rakstīji, un varbūt es vienkārši ne tā uztvēru, tomēr grupu (ciklu) izmēri 2nieku un 3nieku gadījumā atšķirās..

 

Patiesībā arī biju domājis

 

Cikla izmērs = num ^power - num^{(power - 1)}

 

#include <fstream>
using namespace std;
typedef long long ul;
ul n, p;
void getPower(ul , ul*);
int main()
{
       ul power2(0), power3(0);
       ifstream& input = *new ifstream("vienin.in");
       input>>p>>n;
       input.close();
       delete& input;
if(1 != n)
{
 if(p%3)    
   getPower(3, &power3);

 if(p%2)  
 getPower(2, &power2);
}
       ofstream& output = *new ofstream("vienin.out");
       output<<power2<<" "<<power3;
       output.close();
       delete& output;
       return 0;
}
//---------------------------------------------------------------------------
inline void getPower(ul num,  ul* power)
{
ul atl_next, atl, sum_atl, uniqueRemainders, loops, temp_atl,  tempNum(num);

while (1)
 {
       sum_atl = temp_atl = atl_next = atl = p%num;
       uniqueRemainders = 1;
       while (temp_atl != (atl_next = (atl_next * atl) % num) )
       {
      	++uniqueRemainders;
      	sum_atl += atl_next;
       }

	// tikai pilna cikla summa dalas ar nepieciesamo pakapi bez atlikuma un dalejs cikls nekad neveidos atlikumu 0
       if(n % uniqueRemainders)break;  
	loops = n/uniqueRemainders;   // Atlikumu pilno "ciklu" skaits
	if( sum_atl*loops%num) break;	// Si ir preoblemrinda, kaut kaa jaapanaak, lai nevajadzeetu rekinat loops*sum_atl, kas parsniedz tipa izmerus
       else
       {
           *power += 1;
           num *= tempNum;
       }
 }

}

 

 

 

Šis kods olimpā joprojam iztur tikai 9 testus no 10, 6.testā uzrādot kļūdu.

Kā panākt, lai nevajadzētu rēķināt sum_atl*loops, kas var pārsniegt tipa izmēru?

Labots Augusts 9, 2011 - Dunks

[čaks]

Sveiki! Nedaudz offtopic... iedvesmojoties no šī visa, ķēros klāt c++ un uzdevumiem iekš Olimpa. Kāds nevarētu pateikt, kā mainīgajam piešķirt vērtību iekš .in faila. x=... taču nav korekti? Ceru uz jūsu palīdzību šajā muļķīgajā jautājumā.

[0xDEAD BEEF]

Es domaju - tev jauzraksta kada DOM klase, kas deserialize to .in failu kada jauka koka struktura un tad jau vienkarsi un pec tam tikai save.

Beefs

[Dawis]

Sveiki! Nedaudz offtopic... iedvesmojoties no šī visa, ķēros klāt c++ un uzdevumiem iekš Olimpa. Kāds nevarētu pateikt, kā mainīgajam piešķirt vērtību iekš .in faila. x=... taču nav korekti? Ceru uz jūsu palīdzību šajā muļķīgajā jautājumā.

Rekur redzams kā tie inicializēts fails un tiek ielasīti divi mainīgie:

 ifstream& input = *new ifstream("vienin.in");
 input>>p>>n;
 input.close();
 delete& input;

 

rindiņa input>>p>>n; ielasa divus mainīgos vispirms p un pēc tam n.

Labots Augusts 9, 2011 - Dawis

[Dunks]

Rekur redzams kā tie inicializēts fails un tiek ielasīti divi mainīgie:

 ifstream& input = *new ifstream("vienin.in");
 input>>p>>n;
 input.close();
 delete& input;

 

rindiņa input>>p>>n; ielasa divus mainīgos vispirms p un pēc tam n.

 

Tiek inicializēts nevis fails, bet gan klases iftsream objekts input, kurš māk failus lasīt. Pie kam inicializācija notiek dinamiski.

Labots Augusts 9, 2011 - Dunks

[Dawis]

Tiek inicializēts nevis fails, bet gan klases iftsream objekts input, kurš māk failus lasīt. Pie kam inicializācija notiek dinamiski.

Taisnība.. man tikai likās ka cilvēkam, kas prasa, kā nolasīt mainīgo no faila sākumam pietiks ar to ko es uzrakstīju:)

Faktiski taču ir skaidrs, kas domāts ar vārdiem - tiek inicializēts fails, ja komandrindiņa satur faila ceļu.. Tas ko tas zemākā līmenī nozīmē man šoreiz likās otršķirīgi..

 

Var jau būt, ka kļūdos un cilvēks citādā ziņā ir baigais speciālists OO programmēšanā un pointeros, tikai viņam nav ne jausmas kā c++ strādāt ar failiem, bet man kaut kā tā nelikās, ka šis būtu tas gadījums...

 

BTW: Par to dinamisko inicializēšanu - Ievēroju, ka tu visur kur vien vari izmanto pointerus un adreses nevis statiskus (klasiskus) mainīgos? Vai tam ir kāds iemesls, vai tas ir vienkārši tāds stils?

 

 

Šis kods olimpā joprojam iztur tikai 9 testus no 10, 6.testā uzrādot kļūdu.

Kā panākt, lai nevajadzētu rēķināt sum_atl*loops, kas var pārsniegt tipa izmēru?

 

sum_atl*loops noteikti tev nevajag rēķināt..

 

Izmantojot tās pašas atlikumu īpašības tu vari mierīgi ņemt šādi ((sum_atl % num) * (loops % num)) % num

 

Arī pašu sum_atl var rēķināt mazliet taupīgāk (attiecībā uz overflow):

while (temp_atl != (atl_next = (atl_next * atl) % num) )
       {
       ++uniqueRemainders;
       sum_atl += atl_next;
       sum_atl = sum_atl % num.
       }

Problēma ir tāda, ka pats num agri vai vēlu izies ārpus robežām..

 

Bez tam mēs jau nepierādījām, ka ja n nedalīsies ar cikla izmēru (t.i. būs nepilns cikls beigās), ka tas uzreiz nozīmēs ka nedalās - tā tikai liecina mūsu novērojumi, bet vismaz pagaidām pierādīt to es nevaru..

Protams varam to pieņemt, bet gribēju uzsvērt, ka nevaram par to galvot..

Labots Augusts 9, 2011 - Dawis

[čaks]

Rekur redzams kā tie inicializēts fails un tiek ielasīti divi mainīgie:

 ifstream& input = *new ifstream("vienin.in");
 input>>p>>n;
 input.close();
 delete& input;

 

rindiņa input>>p>>n; ielasa divus mainīgos vispirms p un pēc tam n.

 

Par to ielasīšanu es it kā sapratu, bet, lai ielasītu, jābūt taču iepriekš izveidotam failam, no kura ielasa. Ne tā? Un šajā gadījumā tas ir vienin.in, kurā jāpiešķir p un n vērtības. Kā, lai tajā vienin.in norāda šīs vērtības? Uzrakstīju Olimpa vienkāršākā uzdevuma kodu, ieguvu maksimālo vērtējumu, bet pats tā arī nespēju pārbaudīt rezultāta pareizību, jo, acīmredzot, nesaprotami piešķiru vērtību .in failā.