Exponential Growth

Limits 1s, 512 MB

You will be given two integers X and N, you have to calculate XN modulo 1000000007.


This is a companion discussion topic for the original entry at https://toph.co/p/exponential-growth
1 Like

Whats wrong with my code?

#include<stdio.h>
#include<math.h>

int main()
{
    int X,N,b;
    scanf("%d%d",&X,&N);
    b=pow(X,N);
    printf("%d",b);
    return 0;
}
1 Like

You are getting a compilation error.
Looks like the compiler is generating some kind of error known as undefined behavior.

Undefined behavior is something kind of case that was not defined correctly in the header files or does not exist in any kind of documentation.

However, even if I can’t explain how will you handle the problem with C11 compiler now, you can use C++11/14/17 GCC 9.2 to compile to correctly compile it for now.

C++11 or above has additional type overloading versions of pow so they can compile it correctly.

2 Likes

At first glance I thought this could be a an issue with automatic type conversation and the expected type of pow arguments being different from what is provided in the code.

But turns out C11 was not perfectly configured. I have fixed the issue and rejudged all submissions with compilation errors for C11.

Oh! So, it was a misconfigured compiler problem.
I searched for reference to pow and got these declarations. here.

C99

     double pow  (double base     , double exponent);
      float powf (float base      , float exponent);
long double powl (long double base, long double exponent);

C++98

     double pow (double base     , double exponent);
      float pow (float base      , float exponent);
long double pow (long double base, long double exponent);
     double pow (double base     , int exponent);
long double pow (long double base, int exponent);

C++11

     double pow (double base     , double exponent);
      float pow (float base      , float exponent);
long double pow (long double base, long double exponent);
     double pow (Type1 base      , Type2 exponent); 

As you can see, the C++ versions support polymorphism.

I tried to replace int with double but it was still not working.
And thus, I advised him to use a C++ Compiler for now.

Btw, what had gone wrong? @hjr265

1 Like

The math library was not being linked properly for C11.

Hmm, it seems to be a reasonable case. :face_with_monocle:

x, n=map(int, input().split())
xn=x**n
print(xn%1000000007)

Sir how can I reduce the CPU use for test case 2?

The solution for this in Python requires just one line. There is a built in function that does the job.

However, if you want to know the technique that solves this problem, you can read about it here: https://en.wikipedia.org/wiki/Modular_exponentiation

#include<stdio.h>
#include<math.h>
int main(void)
{
 int X,N;
	long double c;
	scanf("%d %d",&X,&N);
	c=pow(X,N);
	long double d=remainder(c,1000000007);
	printf("%.Lf\n",d);
	return 0;
 }

what the problem of this code??

The expected solution of this problem is to use a technique called “modular exponentiation”.

Can you plz tell what is modulo 10000007 ?

কোনো সংখ্যাকে ১০০০০০০০০৭ (১০+৭) দিয়ে ভাগ করার পর যে ভাগশেষ থাকবে সেটা।
The Remainder of a number upon being divided by 1000000007 or 109+7.

In all problems there are some mistakes…
Such as,
10^9 is written as 109.
It is very common in the problems now

1 Like

The statement has been updated. Thanks again for reporting this. @user.660051