Why is my code giving wrong output for testcase : A : 71045970 B : 41535484 C : 64735492


#1

A : 71045970
B : 41535484
C : 64735492

My output: 17948732
Expected output: 20805472

Any help is appreciated.

This is my code:

int Solution::Mod(int A, int B, int C) {
    if (B==1) {
        if (A<0)
            return ((A+C)%C);
        return (A%C);
     } 
    
    if (B==0)
        return (1%C);
    
    long long p = Mod(A,B/2,C);

    if (B%2==0)
        return p*p%C;
    else {
        if (A<0)
            return (p*p*((A+C)%C))%C;
        return (p*p*(A%C))%C;
    }
}

#2

you have your p as long long while A,B,C are int this will cause the result to be a integer
so it is better if you change A ,B, C to long long


#3

assign this to a long long variable like
long long z= p*p;
then
return (z*((A+C)%C))%C;

do this for both occurrences of p*p