- Kôd: Obeleži sve
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
int brojKoraka(int x, int y)
{
int pom;
int cond;
int col;
int ex=0;
int ey=0;
int k=0;
if(x==y) return 0;
/* u x ćemo čuvati vrednost većeg broja. Tako da ako je ulaz 6 10, x će biti 10, a y 6. Zapravo, 10 ćemo svoditi na 6, iako je originalno dato da od 6 treba dobiti 10. Svakako je u pitanju isti broj koraka. */
if(x>y)
{
cond=x%y;
col=x/y;
}
else
{
cond=y%x;
col=y/x;
}
if(cond == 0)
{
while(col%2 == 0)
{
col>>=1;
k++;
}
for (int i = 3; i <= sqrt(col); i = i+2)
{
while (col%i == 0) // % izračunava ostatak pri deljenju levog operanda desnim (analogija MOD u pascalu)
{
col = col/i;
k++;
}
}
k+=(col>2);
}
else
{
while (x%2 == 0)
{
x = x >> 1;
ex++;
}
while(y%2 == 0)
{
y>>=1;
ey++;
}
if(y>x)
{
pom=x;
x=y;
y=pom;
}
k+=abs(ex-ey);
for (int i = 3; i <= sqrt(x); i = i+2)
{
ex=ey=0;
while (x%i == 0)
{
x = x/i;
ex++;
}
if(x==y) return (k+ex);
while(y%i == 0)
{
y/=i;
ey++;
}
if(y>x)
{
pom=x;
x=y;
y=pom;
}
k+=abs(ex-ey);
}
if(x!=y)
k+=(x>2)+(y>2); // izraz (x>2) daje jedinicu ako je x>2, u suprotnom nulu. Isto vazi i za y
}
return k;
}
int main()
{
int n,i,x,y;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",brojKoraka(x,y));
}
return 0;
}
Ukratko, ideja je sledeća. Ako je veći broj deljiv manjim, razložićemo njihov količnik na proste činioce i to će biti broj potrebnih "specijalnih operacija", gde su specijalne operacije definisane na način naveden u zadatku. Ukoliko to nije slučaj, broj specijalnih operacija određujemo kao razliku eksponenata prostih činioca koji ulaze u faktorizacioni oblik jednog od brojeva. Dakle, za ulaz [inlmath]10[/inlmath] [inlmath]6[/inlmath] algoritam bi radio na sledeći način. [inlmath]10=2\cdot5[/inlmath], [inlmath]6=2\cdot3[/inlmath]. Za faktor [inlmath]2[/inlmath] razlika između izložioca je [inlmath]0[/inlmath]. Kako smo oba broja sveli na neparne proste, algoritam stiže do poslednjeg if-a u funkciji vratiBrojKoraka. Kako su obe vrednosti različite i veće od dva, [inlmath]k[/inlmath] će uzeti vrednost [inlmath]2[/inlmath].
For petlja, koja sledi nakon svođenja oba broja na neparne, će se (u najgorem slučaju) izvršavati sve dok obe početne vrednosti ne svede na odgovarajuće najveće proste činioce. Otuda i potreba za pomenutim if-om na kraju.