Why my solution get partially solved?

1

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.

2

It is showing only test details not program. :thinking:

3

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
4

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

5
1 Like
6

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)?

7

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

8

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