M*******a
发帖数: 1633 | 1 Given a credit card number with a certain number of fixed digits and a
certain number of digit placeholders, find the number of solutions such that
the entire number yields a remainder of 3 when divided by 13. Use
properties of modulus | b*****c
发帖数: 1103 | | A*********c
发帖数: 430 | 3 楼上正解。
为扩展，先写一个函数string convert(const int &input, const int &newbase);
然后判断最后一位是不是‘3'
带着这个函数去bruteforce所有的placeholder就行了。
that
【在 M*******a 的大作中提到】
: Given a credit card number with a certain number of fixed digits and a
: certain number of digit placeholders, find the number of solutions such that
: the entire number yields a remainder of 3 when divided by 13. Use
: properties of modulus
| M*******a
发帖数: 1633 | 4 你说每个数字都convert to 13 based，然后看最后位是不是3?
那我为什么不十进制每个数字都看看是不是mod 13 = 3直接？
【在 A*********c 的大作中提到】
: 楼上正解。
: 为扩展，先写一个函数string convert(const int &input, const int &newbase);
: 然后判断最后一位是不是‘3'
: 带着这个函数去bruteforce所有的placeholder就行了。
:
: that
| A*********c
发帖数: 430 | 5 嗯，如果输入是整数的话没必要转换了，舍近求远。
如果输入是一个big integer，估计要转换下，要不整数装不下怎么办。上面函数原型
输入应该string。
【在 M*******a 的大作中提到】
: 你说每个数字都convert to 13 based，然后看最后位是不是3?
: 那我为什么不十进制每个数字都看看是不是mod 13 = 3直接？
| M*******a
发帖数: 1633 | 6 有没有比一个个都算好点的算法阿
【在 A*********c 的大作中提到】
: 嗯，如果输入是整数的话没必要转换了，舍近求远。
: 如果输入是一个big integer，估计要转换下，要不整数装不下怎么办。上面函数原型
: 输入应该string。
| w*******s
发帖数: 138 | 7 直接第推就好了
f(n, m) 为前n个数字余13为m的个数 0 <= n <= 16, 0 <= m < 13
f(16, 3)为答案
【在 M*******a 的大作中提到】
: 有没有比一个个都算好点的算法阿
| b***e
发帖数: 1419 | 8 基本上吧。前面都是0的边界情况需要考虑一下。
【在 w*******s 的大作中提到】
: 直接第推就好了
: f(n, m) 为前n个数字余13为m的个数 0 <= n <= 16, 0 <= m < 13
: f(16, 3)为答案
| r*c
发帖数: 167 | 9 #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));
}
}; | D**********d
发帖数: 849 | 10 觉得可以直接计算而不用 blue force.
思路以例子说明:
assume: XXX123XX
1. 计算每位对 13 的余数，如 1%13 = 1, 10%13= 10, 100%13 = 9 ... etc.
2. 计算在高位余数 i = 0,...,12 时，XX 出现的余数为 3 的个数，e.g. XXX12300
余 0 时，XXX12300 -- XXX12399 间余数为 3 的数的个数是 99/13 = 7 ... 8, 所以
有 7 个。a_0 = 7
3. 利用 (1) 中结果计算 XXX123.. 高位 %13 余数 为 i = 0,...,12 的个数。设为 b
_i,
4. 总个数 \sum_0^{12} a_i * b_i | M*******a
发帖数: 1633 | 11 您说说思路行不？
【在 r*c 的大作中提到】
: #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) {
| M*******a
发帖数: 1633 | 12 您这回答得有点像下列步骤1：
how to draw a face:
1 draw a circle
2 draw the rest of the details
【在 w*******s 的大作中提到】
: 直接第推就好了
: f(n, m) 为前n个数字余13为m的个数 0 <= n <= 16, 0 <= m < 13
: f(16, 3)为答案
| c********p
发帖数: 1969 | | r*c
发帖数: 167 | 14 brute force
【在 M*******a 的大作中提到】
: 您说说思路行不？
|
|
