# Why my solution get partially solved?

Here the question link: A^B mod C - Problems - Eolymp
Here my solution link: Solution #6820222 - A^B mod C - Eolymp
Can anyone explain? @tmwilliamlin @ssjgz @everule1 Can you please tell me.

It is showing only test details not program. It should show my program. ok, no problem. Here my program:

``````try:
while True:
a, b, c = map(int, input().split())
print((a**b)%c)
except:
pass
``````

I think first you should calculate b = b % (c-1) and than power(a,b) %c in log(n) time.

1 Like

ok. this time it give me 5% AC for this solution:
https://www.e-olymp.com/en/submissions/6820271

``````try:
while True:
a, b, c = map(int, input().split())
b = b%(c-1)
print((a**b)%c)
except:
pass
``````

Can you please explain why I need to calculate b = b%(c-1)?

@ssjgz Can you give me some testcases for this problem?

First of all sorry for replying late:

https://www.e-olymp.com/en/submissions/6820493

This is my AC submission.

``````    /*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
ll moduloMultiplication(ll a,ll b,ll c)
{
long long res = 0;
a %= c;
while (b)
{
if (b & 1)
res = (res + a) % c;
a = (2 * a) % c;
b >>= 1;
}
return res;
}
ll power(ll x,ll y,ll p)
{
ll res = 1;
x = x % p;

while (y > 0)
{
if (y & 1)
res = (moduloMultiplication(res,x,p)) % p;
y = y>>1;
x = (moduloMultiplication(x,x,p)) % p;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll a,b,c;
while(cin >>a)
{
cin >> b >> c;
cout << power(a,b,c) << "\n";
}
return 0;
}
``````

Actually, problem here is overflow during multiplication of two large numbers, so we handle them using a separate function.

Only problem with your python code is time of execution is high.

Sorry,I haven’t read question correctly previously and gave wrong suggestion regarding taking modulo with c-1.

BTW, in case you don’t know about taking modulo with c-1, it is required when b is large and can not be stored in memory and valid only when c is prime number. You can read this about here : https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/

1 Like