I submitted my code in python of WITMATH during the contest and got AC. When i was submitting the same using C++ it was giving TLE though i had taken all steps to prevent overflow. Please can anyone help. Here's my part of the code where repeated squarring is done:
~~#include<cstdio>
#include<cstdlib>
~~<pre>
#include<cstdio>
#include<cstdlib>
using namespace std;
~~unsigned long long int mult(unsigned long long int a,unsigned long long int b,unsigned long long int c)
{
~~
unsigned long long int mult (
unsigned long long int a,
unsigned long long int b,
unsigned long long int c
)
{
unsigned long long int x=0,y=a%c;
~~
while(b>0)
{
~~ while(b>0)
{
if(b%2==1)
~~
{
~~ {
x=(x+y);
~~
if(x>c)
~~ if(x>c) x=x%c;
~~}
~~ }
y=(y*2);
~~
if(y>c)
~~ if(y>c) y=y%c;
~~
~~ b/=2;
~~
}
~~ }
return x%c;
~~
}
unsigned long long int modulo( unsigned long long int a, unsigned long long int b, unsigned long long int c)
{
~~}
unsigned long long int modulo (
unsigned long long int a,
unsigned long long int b,
unsigned long long int c
)
{
unsigned long long int x = 1;
~~ ~~unsigned long long int y = a;
~~ ~~while ~~(b>0)
{
~~(b>0)
{
if ~~(b%2==1)
~~(b%2==1) x = mult(x,y,c);
~~ ~~y = mult(y,y,c);
~~ ~~b = b/2;
~~
}
~~}
return x%c;
~~ }
~~}
</pre>