# A^B mod C

Given a , b , c find the value of `a^b` mod c ( 1a , b , c < `2^63` ).

#### Input

Contains multiple test cases. Each test is given in one line and contains three integers a , b and c .

#### Output

For each test case print on a separate line the value of `a^b` mod c .

I use this :

``````#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define lli long long int

lli fast(lli a,lli b,lli mo){
a = a%mo;
lli ans=1;
while(b){
if(b%2)
ans=(ans*1ll*a)%mo;
a=(a*1ll*a)%mo;
b=b/2;
}
return ans;
}

int main(){
lli a,b,c;
while(cin>>a>>b>>c) {
cout<<fast(a,b,c)<<endl;
}
return 0;
}
``````

It only pass 75% , link : Exponentiation - Eolymp

@ssjgz plz see

Please post the actual, full code - this won’t compile Also, note that `a` and `ans` can be up to 2^{63}-2 - multiplying two such numbers will overflow a `long long int`.

1 Like

i updated now plzz see and help me to remove this isssue.

i edit my fast function to this still WA ?

``````lli fast(lli a,lli b,lli mo){
a = a%mo;
lli ans=1;
while(b){
if(b%2)
ans=((ans%mo)*(a%mo))%mo;
a=((a%mo)*(a%mo))%mo;
b=b/2;
}
return ans;
}``````

Here’s a testcase where it fails:

``````5244 887 562949953421311
``````

As to how to solve it: you’re going to have to use a datatype that can hold numbers up to 2^{128}, I guess, or somesuch solution. I don’t know what facilities are available on e-olymp.com, though.

1 Like

yeah but now how can i resolve… ?

i think i have the code in my submissions, look at cgpown. Wait it’s 9e18, I don’t think it will work.

where bro…on cc ??

It will only work maxvalue/81, after that it will overflow. I don’t think there is any standard template. You’ll have to use a digit vector.

so how can i solve for noww ?
and also the no. of test cases i don’t know then how can i covert code to python(as python has issue of overflow)
how can i write this in python

``````while(cin>>a>>b>>c)
``````

?

`map(int,input().split())`
You can search it on the net.

bro i know this syntax i m asking how to take 3 inputs when i don’t know how many test cases were there?

``````try:
while true
#code
except:
pass
``````

infinite loop happens then

Note: Above approach will only work if 2 * m can be represent in standard data type otherwise it will lead to overflow.

Use unsigned long long int for that

wrong … it even gives wrong answer on sample test case EDIT : sorry …yeah its correct … thanks @nishant403 This works fine for sample.

``````#include <bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int unsigned long long

int mult(int a,int b,int mod)
{
int res = 0;

while(b>0)
{
if(b&1) res=(res + a)%mod;
a=(a+a)%mod;
b>>=1;
}

return res;
}

int power(int a,int b,int mod)
{
int res = 1;

while(b>0)
{
if(b&1) res=mult(res,a,mod);
a=mult(a,a,mod);
b>>=1;
}

return res;
}

signed main()
{
int a,b,c;

while(cin >> a >> b >> c) cout << power(a,b,c) << '\n';
}``````
2 Likes

AC verdict 