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. :thinking:

It should show my program. ok, no problem. Here my program:

    while True:
        a, b, c = map(int, input().split())

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:

    while True:
        a, b, c = map(int, input().split())
        b = b%(c-1)

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:


This is my AC submission.

    /*author - Ashutosh Chitranshi*/
    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()
        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