519 Modulo

[•Magnus]

pe sursa asta iei 90?? cred ca glumesti.  

in primul rand: teorema lui Fermat este a^p-1=1(modulo p) (a nedivizibil cu p)
in al doilea rand: teorema este valabila numai pentru p prim

asa ca intrebarea este cum de iei 90.

pe testul 2 3 3, sursa ta da 1, desi raspunsul este 2.

problema se poate rezolva prin ridicare la putere in timp logaritmic
dar avand in vedere dimensiunile mici ale lui c o idee ar fi sa vezi cand apare un ciclu in resturi in O(c) si de aici tot in O(c) sa gasesti raspunsul

l.e.: scuze, nu am vazut postul lui George

[•thesilverhand13]

Am o micuta prooblema:am rezolvat cerinta utilizand ridicarea la putere in timp logaritmic.Cu toate astea iau tle pe testul 9 http://infoarena.ro/job_detail/654803 .Mentionez ca am pus unsigned long long peste tot.Care ar putea fii baiul    ?

[•Stefex09]

si eu folosesc ridicarea la putere in timp logaritmic (cu optimizare pe biti)  si iau TLE pe testul 9... ceva idei?   

[•BLz0r]

Cod:

fscanf (f,"%d%d%d",&a,&b,&c);
	
	a=a%c;
	b=b%c;
	if (a==0 && b==0){
		p=0;
	}
	while (b>0){
		if (b%2==1){
			p=p%c*a%c;
			b--;
		}
		a=a%c*a%c;
		b/=2;
	}
	
	fprintf (g,"%d",p);

iau WA pe testele 7 si 10. imi poate spune cineva unde gresesc sau ce uit va rog?

[•EuBossulet]

Si eu luam WA pe testul 7, la mine era din cauza ca le declarasem variabilele de longint si nu de int64. Cred ca in C++, int 64 este echivalentul la unsigned long long...poti incerca si vezi ce iti da

[•andreiPC]

Problema destul de easy,dar testul 9 e cam hard core. 90 puncte si 

[•andrei_ciobanu]

Imi place   

[•stefanut999]

Asta e Exponentiere rapida(in timp logaritmic) Gasiti indicatii pe arhiva educationala. https://www.infoarena.ro/problema/lgput