CGPOWN - python vs c++ comparison

C++
We multiply each digit seperately and multiply by the corresponding modular power of 10.

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>

using namespace std;
long long int p10[25];
long long int mult(long long int a,long long int b,long long int n){
    int ad[13];
    int bd[13];
     long long int ans=0;
   for(int i=0;i<13;i++){//splitting a and b into digits
       ad[i]=a%10;
       bd[i]=b%10;
       b/=10;
       a/=10;
   }
   for(int s=0;s<25;s++){ // s is the sum of the power of 10
       int i=s;//Their indexes must add up to s for the order of the place value to be s;
       int j=0;
       while(i>=0){
           if(i<13 && j<13){//They need to be less than 13 otherwise out of bounds
            ans+=ad[i]*bd[j]*p10[s]; //multiplying the digits with the corresponding power of 10
            ans=ans%n;
           }
           i--;// going through all possible sums of i&j;
           j++;
       }
   }
   return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin >>t;
	while(t--){
	    long long int a,b,n,ans=1;
	p10[0]=1;
	cin>>a>>b>>n;
    for(int i=1;i<25;i++){ // finding powers of 10 modulo n;
      p10[i]=p10[i-1]*10;
      p10[i]=p10[i]%n;
    }
	    
	    a=a%n;
	    while(b){ //power still left
	        if(b%2){              // if its a one in binary form, multiply by this power of a
	            ans=mult(ans,a,n);
	            ans=ans%n;
	            b--;
	        }
	        a=mult(a,a,n);   //doubling the exponent to the next power of 2
	        a=a%n; 
	        b/=2;//To go to the next binary digit of b      
	    }
	   cout<<ans%n<<"\n"; 
	}
	
}

Python
No explanation needed

for t in range(int(input())):
    a,b,n=map(int,input().split())
    print(pow(a,b,n))

https://www.codechef.com/viewsolution/29820046 :slight_smile:

4 Likes

I guess theres still a lot I don’t know, but what is the boost header file, and the arguments in int main for?

The boost headers are just for the Boost Arbitrary Precision Data Type stuff.

The arguments to main are the standard (optional) arguments, generally used to provide command-line arguments to your program, etc. I don’t actually use them here, so could have omitted them.

2 Likes