generated from sigonasr2/CPlusPlusProjectTemplate
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
36 lines
970 B
36 lines
970 B
#include "utils.h"
|
|
#include <cmath>
|
|
|
|
std::map<internal::PowModStruct,int>utils::mapping;
|
|
|
|
long utils::PowMod(int a,int b, int mod){
|
|
int shift=0;
|
|
long product=0;
|
|
for(long n=1;n<=b;n*=2){
|
|
if(utils::mapping.find({a,n,mod})!=utils::mapping.end()){
|
|
if(b&n){
|
|
if(product==0){
|
|
product=1;
|
|
}
|
|
std::cout<<utils::mapping[{a,n,mod}]<<std::endl;
|
|
product*=utils::mapping[{a,n,mod}];
|
|
product%=mod;
|
|
}
|
|
continue;
|
|
}
|
|
if(n==1){
|
|
utils::mapping[{a,n,mod}]=a%mod;
|
|
}else{
|
|
utils::mapping[{a,n,mod}]=long(utils::mapping[{a,n/2,mod}])*utils::mapping[{a,n/2,mod}]%mod;
|
|
}
|
|
if(b&n){
|
|
if(product==0){
|
|
product=1;
|
|
}
|
|
product*=utils::mapping[{a,n,mod}];
|
|
product%=mod;
|
|
}
|
|
shift++;
|
|
}
|
|
return product%mod;
|
|
} |