519 Modulo

[•wefgef]

Fii mai coerent in posturi ca nu esti ceausescu la balcon sa ne iei cu alooo. Eventual citeste documentatia, uita-te in evaluator ca sa vezi ce erori ai, compileaza cu altceva, nu cu Borland, si apoi posteaza sa vedem daca e vreo diferenta.

[•DITzoneC]

Si eventual asculta si sfaturile care ti se dau.

[•andrici_cezar]

am neovie de ajutor am citit tot ce sa scris pe acest topic si n u imi iese ... de ce??? nu stiu sa ma ajute si pe mn cineva cca nu mai suport sa iau 0 puncte

[•DITzoneC]

Cateva observatii:

* tu aici citesti doar a

Cod:

f>>a,b,c;  

Eventual pune

Cod:

f>>a>>b>>c;  

* in cadrul acestui for tu nu faci nimic pentru ca ai pus ; intre for si instructiune, deci la tine mereu m = a;

Cod:

 for (i=1;i<=b;i++);  
     m=m*a;  

* Complexitatea ta este O(b) care o sa iasa din timp in momentul in care intructiunea din acel for nu va mai fi vida. Incearca sa te uiti peste Problema asta pentru a obtine o complexitate O(log B).

[•andrici_cezar]

mersi amreusit sa iau 100 

[•jupanu92]

Eu am facut acelasi algoritm ca la ridicare la putere in timp logaritmic si dupaia am afisat sol%q si iau incorect pe toate

[•devilkind]

numarul A^B s-ar putea sa fie putin cam mare, nu crezi ca iti depaseste tipul de date care il folosesti, oricare ar fi acela.

[•jupanu92]

Gata , am rezolvat problema asta era mersi !

[•Magnus]

Cod:

#include <stdio.h>

long fct(long a,long A,long b,long c)
{
 if (b<3) return a*a%c;
 else if (b<4) return a*a*a%c;
 else
 {
  a=fct(a,A,b/2,c);
  a=a*a%c;
  if (b%2==1) a=a*A%c;
  return a;
 }
}

int main()
{
 long a,b,c,A;
 freopen("modulo.in","r",stdin);
 freopen("modulo.out","w",stdout);
 scanf("%ld%ld%ld",&a,&b,&c);
 a=a%c;
 A=a;
 if (b>1) a=fct(a,A,b,c);
 printf("%d",a);
 return 0;
}

stie cineva de ce iau doar 40 pct?

[•toni2007]

Din cate imi aduc aminte, rezultatul trebuia tinut pe long long.

[•Magnus]

ms mult
a mers

[•Alexa_ioana_14]

LA fiecare reapelare de functie am facut modulul...si totusi pe ultimele 2 teste iau WA...
if (p==0) return 1;
if (p%2) return (n%m)*putere((n%m)*(n%m),p/2)%m;
return putere((n%m)*(n%m),p/2)%m;
unde n=a, p=b, m=c
unde gresesc?

[•pcinfo]

încearca ca în loc de

a^b = (a*a)^b/2  pentru b par

să foloseşti

a^b = a^b/2 * a^b/2

evident pe a^b/2 îl calculezi o singură dată şi îl memorezi... cel puţin la mine a mers

[•Alexa_ioana_14]

ok, mersi mult!

[•miculprogramator]

Am creat o functie.

Cod:

long long int put(long int a,long int b,long int c)
    {
    int rez,aux;
    if (b%2!=0) aux=pow(a,b-1)*a;
       else aux=pow(a,b/2)*pow(a,b/2);
    rez=aux%c;
    return rez;
    }

Iau 0 puncte pe rezolvarea mea. Ce as putea optimiza, am citit topicul si am aplicat ceea ce am gasit. What's the problem? 

[•klamathix]

Am creat o functie.

Cod:

long long int put(long int a,long int b,long int c)
    {
    int rez,aux;
    if (b%2!=0) aux=pow(a,b-1)*a;
       else aux=pow(a,b/2)*pow(a,b/2);
    rez=aux%c;
    return rez;
    }

Iau 0 puncte pe rezolvarea mea. Ce as putea optimiza, am citit topicul si am aplicat ceea ce am gasit. What's the problem? 

Cod:

  if (b%2!=0) aux=pow(a,b-1)*a;
       else aux=pow(a,b/2)*pow(a,b/2);

pow-ul e problema.

[•miculprogramator]

Sa incerc intr-un for ? 

Edit:

Asa?

Cod:

long long int put(long int a,long int b,long int c)
    {
    int rez,aux=1,i;
    if (b%2!=0) 
       {
       for (i=1;i<=b-1;i++)
           aux*=a;
       aux*=a;
       }
    else 
         {
         for (i=1;i<=b/2;i++)
             aux*=a;
         for (i=1;i<=b/2;i++)
             aux*=a;
         }
    rez=aux%c;
    return rez;
    }

Sau exista o metoda mai buna?

[•klamathix]

Nu , mai . B-ul e pana in 1 << 32 pow ( a ,  b/2 ) e urias , degeaba ai facut functia aia daca folosesti pow . Ideea e sa fie recursiva ( desi nu neaparat ) si sa scapi de problema asta. Uita-te pe ridicare la putere in timp logaritmic , ai si surse acolo . Si mai uita-te si pe restul topicului...

[•miculprogramator]

Multumesc mult pentru ajutor, a iesit ! 

[•robigi]

doar ca fapt divers as intreba de ce solutia asta ia 90 pct cu TLE pe testul 9?

Cod:

cv=a;
	for (int i=0; (1<<i)<=b; ++i)
	{
		if (((1<<i)&b)>0)
			sol=(sol*cv)%c;
		cv=(cv*cv)%c;
            }

sper ca nu ajut prea mult cu codu asta, dar daca da rog un admin sa-l stearga

[•pauldb]

Daca b > 2^30, atunci i-ul ar ajunge 31, dar 2^31 iese din int si se face overflow.

[•robigi]

a' da chiar  ,  mersi
ar fi trebuit sa pun unsigned int32 ca sa intre

[•laurion]

dupa lupte seculare  am reusit sa imi dau seama de ce luam numai 90p, pt ca declaram variabilele "register unsigned long long int"
putin ciudat, dupa ce am sters "register" am luat 100
sunt curios de ce 

[•alex_ovidiunitu]

sursa mea ia 90 de puncte (iau WA pe testul 7 ) .
imi puteti spune ce e gresit aici:

Cod:

        p=1;
	f>>a>>b>>c;
	for(i=1;i<=b%c;i++)
		p=(p*(a%c))%c;
	g<<p%c; 

[•PlayLikeNeverB4]

Verifica posturile anterioare.

pt a=4, b=4, c=4 iti afiseaza 1, iar rez e 0...deci e doar o coincidenta ca iei atat de mult, deoarece (a^b)mod(c) nici in o mie de ani nu va fi (a mod c)^(b mod c), adica principiu pe care spui tu ca te bazezi