E-olmpic question

general
1

A^B mod C

Given a , b , c find the value of a^b mod c ( 1 ≤ a , 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

2

Please post the actual, full code - this won’t compile :slight_smile:

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
3

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

4

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;
 }
5

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
6

yeah but now how can i resolve… ?

7

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

8

where bro…on cc ??

9

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.

10

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)

?

11

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

12

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

13 
try:
   while true
     #code
except:
  pass
14

infinite loop happens then

15

You can find your answer Here

16

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

17

Use unsigned long long int for that

18

wrong … it even gives wrong answer on sample test case :frowning:
EDIT : sorry …yeah its correct … thanks @nishant403 :slight_smile:

19

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
20

AC verdict :slight_smile: