CF1389E-Calendar Ambiguity

题目:

题目描述:

Berland year consists of $ m $ months with $ d $ days each. Months are numbered from $ 1 $ to $ m $ . Berland week consists of $ w $ days. The first day of the year is also the first day of the week. Note that the last week of the year might be shorter than $ w $ days.

A pair $ (x, y) $ such that $ x < y $ is ambiguous if day $ x $ of month $ y $ is the same day of the week as day $ y $ of month $ x $ .

Count the number of ambiguous pairs.

输入格式:

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of testcases.

Each of the next $ t $ lines contains three integers $ m $ , $ d $ and $ w $ ( $ 1 \le m, d, w \le 10^9 $ ) — the number of months in a year, the number of days in a month and the number of days in a week.

输出格式:

Print $ t $ integers — for each testcase output the number of pairs $ (x, y) $ such that $ x < y $ and day $ x $ of month $ y $ is the same day of the week as day $ y $ of month $ x $ .

样例:

样例输入 1:

1
2
3
4
5
6

5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324

样例输出 1:

1
2
3
4
5

6
9
5
0
116461800

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include "ybwhead/ios.h"
long long gcd(long long a, long long b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        long long m, d, w;
        yin >> m >> d >> w;
        w /= gcd(d - 1, w);
        long long x = min(m, d);
        yout << (x / w) * (x / w + 1) * (x % w) / 2 + (x / w) * (x / w - 1) * (w - x % w) / 2 << endl;
        // cout << x / w << ' ' << x / w - 1 << " " << x - x % w << endl;
    }
    return 0;
}