数据范围的坑

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.

What is the least number of flagstones needed to pave the Square? It’s allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It’s not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

Input

The input contains three positive integer numbers in the first line: n,  m and a (1 ≤  n, m, a ≤ 10^9).

Output

Write the needed number of flagstones.

Examples

Input:

6 6 4

Output:

4

Code

#include <bits/stdc++.h>
using namespace std;

// #define usefre
#define ll long long
#define ull unsigned long long

int main()
{
#ifdef usefre
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    ull n, m, a;
    cin >> n >> m;
    if (n < m)
    {
        a = m;
        m = n;
        n = a;
    }
    cin >> a;
    ull ans = 0;
    ans += (n / a) * (m / a);
    if ((n - n / a * a) < a && (n - n / a * a))
    {
        ans += m / a;
    }
    if ((m - m / a * a) < a && (m - m / a * a))
    {
        ans += n / a;
    }
    if ((n - n / a * a) < a && (m - m / a * a) < a && (m - m / a * a) && (n - n / a * a))
    {
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Summraize

这是Virtual Judge里的一道题。写代码的时候非常顺，然而一直不能AC。后来发现是ans的问题。题目要求中ans是小于10^9；然而int类型：-2^16~2^15-1<10^9。改正后，使用unsigned long long型，AC了。

数据类型	最大值	最小值
int	2^15-1=32767	-2^15=-32768
unsigned int	2^16-1=65535	0
long	2^31-1=2147483647	-2^31=-2147483648
unsigned long	2^32-1=4294967295	0
long long	2^63-1=9223372036854775807	-2^63=-9223372036854775808
unsigned long long	2^64-1=1844674407370955165	0