#include
#include
#include
#include
#include
using namespace std;
class KModulo {
public:
int numSolutions(const string& s, const int m, const int rmd, vector<
string>& res) {
int len = s.size();
int localM = m, mLen = 0;
while(localM){
localM /= 10, ++mLen;
}
if (len < mLen) return 0;
vectorvIndices;
unordered_mapmp; //[index of s, index of vIndices]
for (int i = len-1; i >=0; --i){
if (s[i] == 'x'){
vIndices.push_back(i);
mp.insert(make_pair(i, vIndices.size() - 1));
}
}
vectorvPlaceHolders(vIndices.size(), '0');
int curr = 0;
find(s, m, rmd, curr, vIndices, vPlaceHolders, mp, res);
return res.size();
}
int getRemainderWithPow(int b, int p, int m){
int r = 1;
for (int i = 1; i <= p; ++i)
r = (r * b) % m;
return r;
}
bool checkIfValidIntegralString(const string& s, const int m, const int
rmd)
{
int len = s.size();
int runningTotal = 0;
for (int i = len-1; i >= 0; --i)
runningTotal += ((int)(s[i]-'0') * getRemainderWithPow(10, len-i
-1, m)) % m;
runningTotal %= m;
return runningTotal == rmd;
}
void find(const string s, const int m, const int rmd, int curr,
const vectorvIndices, vector& vPlaceHolders,
const unordered_mapmp, vector& res)
{
if (curr == vIndices.size() - 1){
CheckAndCombine(s, m, rmd, vIndices, vPlaceHolders, mp, res);
return;
}
for (int i = 0; i <= 9; i++){
if (mp.at(vIndices[curr]) == 0 && i == 0) continue; //no zero
for the 1st digit of resulting string
vPlaceHolders[curr] = (char)(i + '0');
find(s, m, rmd, curr + 1, vIndices, vPlaceHolders, mp, res);
vPlaceHolders[curr] = '0';
}
}
void CheckAndCombine(const string src, const int m, const int rmd, const
vectorvIndices,
vector& vPlaceHolders, const unordered_mapmp, vector
& res){
assert(vIndices.size() == vPlaceHolders.size());
int len = src.size();
string s("");
for (int i = len - 1; i >= 0; --i){
if (isdigit(src[i])){
s.append(1, src[i]);
}
else
s.append(1, vPlaceHolders[mp.at(i)]);
}
if (checkIfValidIntegralString(s, m, rmd))
res.push_back(s);
}
void Test()
{
TestGetRemainderWithPow();
TestModulo();
Test1();
Test2();
}
void TestHelper(string fileName, string s, int m, int rmd){
ofstream ofs;
ofs.open(fileName);
ofs << "string: " <"<vectorres;
int nRes = numSolutions(s, m, rmd, res);
for (int i = 0; i < res.size(); ++i){
assert(checkIfValidIntegralString(res[i], m, rmd));
ofs << res[i] << endl;
}
cout << "total number of solutions for " << s << " is " << nRes <<
endl;
ofs << "total number of solutions is " << nRes << endl;
ofs.close();
}
void Test2(){
TestHelper("test2.txt", "x402589303xx44x9", 13, 3);
}
void Test1(){
string s= "x402589303xx44x9";
TestHelper("test1.txt", s, 13, 7);
}
void TestGetRemainderWithPow(){
int r = getRemainderWithPow(10, 5, 13);
assert(r == 4);
r = getRemainderWithPow(10, 10, 13);
assert(r == 3);
r = getRemainderWithPow(10, 6, 13);
assert(r == 1);
}
void TestModulo(){
string s = "3400739803001112";
int m = 13, rmd = 0;
assert(checkIfValidIntegralString(s, 13, 0));
}
};
