圣诞节后衣服会不会更便宜？# Fashion - 美丽时尚
y*n
1 楼
原题在这里。 http://www.mitbbs.com/article_t/JobHunting/32517841.html 但是觉得不太对
搞这些题觉得很没思路。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector calculate(unsigned long m, unsigned long n, int k) {
if(k == 0) {
return vector(1, 1);
} else if(k % 2) { // odd number
vector tmp(1, m);
vector result1 = calculate(m, n-1, k);
return multiplyArrays(result1, tmp, k);
} else {
vector result1 = calculate(m, n/2, k);
return multiplyArrays(result1, result1, k);
}
}
vector multiplyArrays(const vector &data1, const
vector &data2, int k) {
vector result;
int sz1 = data1.size();
int sz2 = data2.size();
for(int i=0; i
for(int j=0; j
if(i+j+1 > k)
break;
const char value = data1[i] * data2[j];
//if(result.size() < i+j+1) {
while(result.size() < i+j+1) {
result.push_back(0);
}
value += result[i+j] + carry;
carry = value/10;
result[i+j] = value % 10;
}
if(i+sz2<=k && carry) {
while(result.size() < i+sz2) {
result.push_back(0);
}
result[i+sz2-1] += carry;
}
}
return result;
}
搞这些题觉得很没思路。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector
if(k == 0) {
return vector
} else if(k % 2) { // odd number
vector
vector
return multiplyArrays(result1, tmp, k);
} else {
vector
return multiplyArrays(result1, result1, k);
}
}
vector
vector
vector
int sz1 = data1.size();
int sz2 = data2.size();
for(int i=0; i
for(int j=0; j
if(i+j+1 > k)
break;
const char value = data1[i] * data2[j];
//if(result.size() < i+j+1) {
while(result.size() < i+j+1) {
result.push_back(0);
}
value += result[i+j] + carry;
carry = value/10;
result[i+j] = value % 10;
}
if(i+sz2<=k && carry) {
while(result.size() < i+sz2) {
result.push_back(0);
}
result[i+sz2-1] += carry;
}
}
return result;
}
