2204C.md (2093B)
1 Source: https://codeforces.com/problemset/problem/2204/C 2 3 C. Spring 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Alice, Bob, and Carol visit a spring to collect water. Alice visits every $a$ days (on days $a, 2a, 3a, \dots$), Bob visits every $b$ days (on days $b, 2b, 3b, \dots$), and Carol visits every $c$ days (on days $c, 2c, 3c, \dots$). 22 23 When only one person visits, they collect $6$ liters of water. If multiple people visit, the water is divided equally: two people take $3$ liters each, and three people take $2$ liters each. 24 25 Your task is to calculate how much water Alice, Bob, and Carol collect over $m$ days, starting from day $1$. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The only line of each test case contains four integers $a$, $b$, $c$, and $m$ ($1 \le a, b, c \le 10^6$; $1 \le m \le 10^{17}$). 32 33 Output 34 35 For each test case, print three integers — the number of liters of water that Alice, Bob, and Carol collect over $m$ days. 36 37 Example 38 39 Input 40 41 ``` 42 4 43 44 2 1 3 10 45 46 1 1 8 5 47 48 6 20 15 1000 49 50 650650 1092 157437 100000000000000000 51 ``` 52 53 Output 54 55 ``` 56 14 38 8 57 58 15 15 0 59 60 881 236 281 61 62 845294870595 549337065358857 3774389867286 63 ``` 64 65 Note 66 67 Consider the first example: 68 69 * on day $1$, only Bob visits the spring, and he collects $6$ liters; 70 * on day $2$, Alice and Bob visit the spring, and they each collect $3$ liters; 71 * on day $3$, Bob and Carol visit the spring, and they each collect $3$ liters; 72 * on day $4$, Alice and Bob visit the spring, and they each collect $3$ liters; 73 * on day $5$, only Bob visits the spring, and he collects $6$ liters; 74 * on day $6$, Alice, Bob, and Carol visit the spring, and they each collect $2$ liters; 75 * on day $7$, only Bob visits the spring, and he collects $6$ liters; 76 * on day $8$, Alice and Bob visit the spring, and they each collect $3$ liters; 77 * on day $9$, Bob and Carol visit the spring, and they each collect $3$ liters; 78 * on day $10$, Alice and Bob visit the spring, and they each collect $3$ liters.