Dotaz: Urychleni jednoducheho algoritmu napsaneho v cecku

[Bundas]

Zdravim. prohlednete si tento zdrojak:

 long long int a, b, x, y, k=0, i=1;
 int main(){
 scanf("%lld %lld %lld %lld", &a, &b, &x, &y);
 FILE *s;
 s = fopen("reseni.txt", "w+");
 printf("\npostup: \n\n");
 long long int z = a/100;
 long long int p = z*i;
 do{
     if((a%x)==0 && (a%y)==0){
         printf("Nalezeny pocet reseni: %lld\n", k);
         k++;
     }
     if(a == p){
         printf("jsem v %lld procentech", i);
         i++;
     }

     a++;
 }while(a != b+1);

 printf("\n%lld\n\n", k);
 fprintf(s, "%lld", k);
 return 0;
 }

na vstupu mam ziskat rozmezi cisel a-b a potom delitele x a y; kdyz je nejake cislo z rozmezi a-b delitelne obema deliteli x a y, tk je k++;

jenze, kdyz je na vstupu rozmezi cisel A az B 858 miliard, tak to muj comp do konce zivota nestihne. Nevite, jak to podstatne urychlit?

diky za pomoc vsem!:D

---

---

Odpovědi

[xxxxxx]

No už jsem dlouho neprogramoval, ale pokud k má být počet čísel mezi a a b, které mají být dělitelné součinem x*y, tak by to mělo být napřímo.

k = b/(x*y)-a/(x*y)

bez žádných cyklů. (tedy doufám, že v integer dělení A/B se mi fakticky provede floor(A/B) tedy dostanu celočíselnou část toho podílu.)

[Bundas]

Cisla v intervalu a a b nemaji byt delitelna soucinem x*y, ale soucasne cislem x a y. Tve reseni funguje tedy spravne pouze pro nesoudelna x a y. Spravne reseni by bylo

k = b/lcm(x,y)-a/lcm(x,y)

long long int
gcd (long long int a, long long int b)
{
  if (!b) return a;
  return gcd(b, a % b);
}

int
main (void)
{
  long long int a, b, x, y, k, lcm;
  FILE *s;
  scanf("%lld %lld %lld %lld", &a, &b, &x, &y);
  s = fopen("reseni.txt", "w+");
  lcm = x * y / gcd(x, y);
  k = b/lcm - a/lcm;
  printf("\n%lld\n\n", k);
  fprintf(s, "%lld", k);
  return 0;
}

[lertimir]

OK

[Bundas]

preloz mi prosim do cestiny if(!b)

[s]

Je to ekvivalent delsiho zapisu if (b == 0).

[mess]

Místo abys testoval každé jednotlivé číslo z toho rozmezí, zkus vynásobit x*y a vyzkoušet, jestli výsledek leží v daném rozmezí. Něco jako tohle:

int i;
for(i = 1; i*x*y < b; i++){
  k++;
}

Samozřejmě ten kód nahoře není dokonalý a chce to ošetřit okrajové podmínky pečlivěji (např. inicializovat i tak, aby první výsledek vycházel do daného rozmezí), ale jako ukázka to stačí. Taky pozor na záporná x a y.

P.S. trochu mi to smrdí školním domácím úkolem. Tak bych se nedivil, kdyby tě s tím někdo poslal do míst, kam slunce nesvítí.

[Bundas]

diky za radu.

skolni ukol to neni. chodim na osmilety gympl a tam nic o programovani v zivote neslyseli.

[Bundas]

divne je, ze kamarad s Woknama a podobne vykonnym CPU to dal za 60s. me to na linuxu bezi uz hodinu a nic. nemuze to byt nejakym vnejsim vlivem linuxu? zkousel sem i nastavit prioritu procesu = bezvysledne

[lertimir]

pokud a není 1 ale nějaké velké číslo tak to nebude fungovat. muselo by se začít cyklus

for(i = ((a/x/y*x*y==a)?a/x/y:a/x/y+1); i*x*y < b; i++){

[s]

Tohle pro nesoudelna x,y nenajde vsechna reseni. Navic je to zbytecne slozite. Da se to udelat v konstantnim case (viz nahore).

[lertimir]

Nějak jsem na ty soudělná x,y pozapoměl.

[axel]

jak uz bylo uvedeno vyse, toto neni spravne reseni bez ohledu na to, kde cyklus zacne

[Jirka]

pánové a tomuhle říkáte řešení? dovolte, abych vás upozornil, že existuje číslo, které je dělitelné x a y a přitom může být menší než x*y. říká se mu nejmenší společný násobek. čili ve výše uvedených postupech je třeba uvažovat n.s.n a ne součin.