1 /************************************************************** 2     Problem: 2045 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:360 ms 7     Memory:9596 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 typedef long long ll;16 const int N = 1000005;17 int u[N], p[N], tot;18 bool v[N];19  20 inline int read(){21     int x = 0;22     char ch = getchar();23     while (ch < ‘0‘ || ch > ‘9‘)24         ch = getchar();25          26     while (ch >= ‘0‘ && ch <= ‘9‘){27         x = x * 10 + ch - ‘0‘;28         ch = getchar();29     }30     return x;31 }32  33 void pre_work(){34     u[1] = 1;35     int i, j, K;36     for (i = 2; i < N; ++i){37         if (!v[i])38             p[++tot] = i, u[i] = -1;39         for (j = 1; i * p[j] < N && j <= tot; ++j){40             v[K = i * p[j]] = 1;41             if (i % p[j] == 0){42                 u[K] = 0; 43                 break;44             }else u[K] = -u[i];45         }46     }47     for (i = 2; i < N; ++i)48         u[i] += u[i - 1];49 }50  51 ll work(int n, int m, int k){52     n /= k, m /= k;53     if (n > m) swap(n, m);54     ll res = 0;55     int i, last;56     for (i = 1; i <= n; i = last + 1){57         last = min(n / (n / i), m / (m / i));58         res += (ll) (u[last] - u[i - 1]) * (n / i) * (m / i);59     }60     return res;61 }62  63 int main(){64     pre_work();65     int a = read(), b = read(), k = read();66     printf("%lld\n", work(a, b, k));67     return 0;68 }