I wrote two solutions for this problem. Both them got AC in C++ while getting TLE in Python. Could somebody give some tips to me to let me pass the test with Python?
Solution 1 (C++/203 ms)
#include <cmath>
#include <iostream>
#define MAX 1000001
using namespace std;
int main(int argc, char ** argv) {
int a, b, c, ans = 0;
cin >> a >> b >> c;
static int D[MAX] = {1, 1};
for (int i = 1; i < a + 1; i++) {
for (int j = 1; j < b + 1; j++) {
for (int k = 1; k < c + 1; k++) {
int l = i * j * k;
if (!D[l]) {
long double sqi = sqrtl(l);
unsigned long long int sum = 0;
for (int m = 2; m < (int) sqi + 1; m++) {
if (!(l % m)) {
if (sqi == m) {
sum++;
continue;
}
sum += 2;
}
}
D[l] = sum + 2;
}
ans += D[l];
}
}
}
cout << ans % (1 << 31) << endl;
return 0;
}
Solution 2 (C++/218 ms)
#include <iostream>
#define MAX 1000001
using namespace std;
int main(int argc, char ** argv) {
int a, b, c, ans = 0;
static int D[MAX];
for (int i = 1; i < MAX; i++) {
for (int j = i; j < MAX; j += i) {
D[j]++;
}
}
cin >> a >> b >> c;
for (int i = 1; i < a + 1; i++) {
for (int j = 1; j < b + 1; j++) {
for (int k = 1; k < c + 1; k++) {
ans += D[i*j*k];
}
}
}
cout << ans << endl;
return 0;
}
--
Solution 1 (Python/TLE)
a, b, c = map(int, raw_input().split())
d = {}
ans = 0
d[1] = 1
for ai in xrange(1, a + 1):
for bi in xrange(1, b + 1):
for ci in xrange(1, c + 1):
i = ai * bi * ci
if i not in d:
sqi = i ** 0.5
d[i] = sum(2 if j != sqi else 1 for j in xrange(2, int(sqi) + 1) if i % j == 0) + 2
ans += d[i]
print ans % 1073741824
Solution 2 (Python/TLE)
a, b, c = map(int, raw_input().split())
m = a * b * c + 1
d = [1] * m
ans = 0
for i in xrange(2, m):
for j in xrange(i, m, i):
d[j] += 1
for ai in xrange(1, a + 1):
for bi in xrange(1, b + 1):
for ci in xrange(1, c + 1):
ans += d[ai*bi*ci]
print ans % 1073741824
Update
Finally pass it in 578 ms with Python.