Question

Enunț
Moca dorește să posteze pe Pbinfo a probleme de dificultate b. Durata postării celor a probleme de dificultate b este restul împărțirii lui ab la 1999999973.

Cerinta
Ajutați-l pe Moca să calculeze durata postării celor a probleme de dificultate b .

Date de intrare
Fișierul de intrare moka.in conține pe prima linie numerele a b, cu semnificația din enunț.

Date de ieșire
Fișierul de ieșire moka.out va conține pe prima linie numărul S, reprezentând restul împărțirii lui ab
la 1999999973.

Restricții și precizări
2 ≤ a,b ≤ 4294967296

Ajutor, imi da 90 de puncte pentru solutia :
#include
using namespace std;
ifstream cin("moka.in");
ofstream cout("moka.out");
long long a,b,z;
int main()
{
cin>>a>>b;
z=1;
while(b)
{
if(b%2==1)
z=z*a%1999999973;
a=a*a%1999999973;
b/=2;
}
cout< return 0;
}

Answer 1

Răspuns:

#include<bits/stdc++.h>

using namespace std;

 

ifstream in("moka.in");

ofstream out("moka.out");

 

unsigned long long puterel(unsigned long long a, unsigned long long b)

{

   unsigned long long z[1001],p=a,i,c=0;

   while(b)

   {

       z[++c]=b%2;

       if(b%2==1)

           b--;

       else

           b/=2;

   }

   for(i=c-1;i>=1;i--)

   {

       if(z[i]==1)

           p=(p%1999999973*a%1999999973)%1999999973;

       else

           p=(p%1999999973)*(p%1999999973)%1999999973;

      // p=p%1999999973;

   }

   return p;

}

 

 

int main()

{

   unsigned long long x,y,c;

   in>>x>>y;

   c=puterel(x,y);

   out<<c;

   return 0;

}

Explicație: