Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Friday, September 6, 2013
SPOJ : Solution to raise the power of a number (Complexity matters here)
Question :
Do you know how to calculate "A" raised to the power "B"? Ofcourse you know. What if "B" becomes very large? answer will be huge, so just calculate the answer modulo 1,000,000,007. Can you do it? Lets see.
Do you know how to calculate "A" raised to the power "B"? Ofcourse you know. What if "B" becomes very large? answer will be huge, so just calculate the answer modulo 1,000,000,007. Can you do it? Lets see.
Inputs
First line will contain "T" the no. of test cases. Each of the next "T" lines will contain two integers "A" and "B".
First line will contain "T" the no. of test cases. Each of the next "T" lines will contain two integers "A" and "B".
Outputs :
For each test case, print "A" raised to the power "B" modulo 1,000,000,007 in a separate line. (Modulo operation gives the remainder, for ex. 5 mod 3 = 2, 10 mod 2 =0, etc. )
For each test case, print "A" raised to the power "B" modulo 1,000,000,007 in a separate line. (Modulo operation gives the remainder, for ex. 5 mod 3 = 2, 10 mod 2 =0, etc. )
Constraints :
1 <= T <= 10^4, 0 <= A <= 10^18, 0 <= B <= 10^18, A and B won't be 0 simultaneously.
1 <= T <= 10^4, 0 <= A <= 10^18, 0 <= B <= 10^18, A and B won't be 0 simultaneously.
Level : Medium
Solution to the Problem :
#include<stdio.h>
long long int mod=1000000007;
long long int mul(long long int a,long long int b)
{
long long int c;
c=mul(a,b/2);
if(b%2==0)
return (2*c)%mod;
return ((2*c)+a)%mod;
}
long long int pow(long long int a,long long int b)
{
if(b==0)
return 1;
if(a==0)
return 0;
if(a==1)
return 1;
long long int x=pow(a,b/2);
if(b%2==0)
return (x*x)%mod;
return (((x*x)%mod)*a)%mod;
}
main()
{
long long int t;
scanf("%lld",&t);
while(t--)
{
long long int a,b;
scanf("%lld%lld",&a,&b);
printf("%lld\n",pow(a%mod,b));
}
}
No comments :
Post a Comment