Блог пользователя changyuheng

Автор changyuheng, 12 лет назад, По-английски

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.

http://www.codeforces.com/contest/236/submission/2419288

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

both solutions have complexity O(abc/2 + abc/3 + ... + abc/abc) > 10^8 iterations when a=b=c=100. python is too slow to pass the tests with such solution complexity.

to calculate all the divisors of n=ijk you need to know factorization of each multiplier value (i,j,k).

when you know that n = 2^res[2] + 3^res[3] + 5^res[5] + 7^res[7] + ... + 97^res[97] (where res[p] is equal to sum of powers of p in factorization i,j,k), the count of divisors will be k=(res[2]+1)*(res[3]+1)*(...)*(res[97]+1)