Plus Minus Permutation (Codeforces 1872D)
Tags: Math, math

You are given $$$3$$$ integers — $$$n$$$, $$$x$$$, $$$y$$$. Let's call the score of a permutation$$$^\dagger$$$ $$$p_1, \ldots, p_n$$$ the following value:$$$$$$(p_{1 \cdot x} + p_{2 \cdot x} + \ldots + p_{\lfloor \frac{n}{x} \rfloor \cdot x}) - (p_{1 \cdot y} + p_{2 \cdot y} + \ldots + p_{\lfloor \frac{n}{y} \rfloor \cdot y})$$$$$$In other words, the score of a permutation is the sum of $$$p_i$$$ for all indices $$$i$$$ divisible by $$$x$$$, minus the sum of $$$p_i$$$ for all indices $$$i$$$ divisible by $$$y$$$.You need to find the maximum possible score among all permutations of length $$$n$$$.For example, if $$$n = 7$$$, $$$x = 2$$$, $$$y = 3$$$, the maximum score is achieved by the permutation $$$[2,\color{red}{\underline{\color{black}{6}}},\color{blue}{\underline{\color{black}{1}}},\color{red}{\underline{\color{black}{7}}},5,\color{blue}{\underline{\color{red}{\underline{\color{black}{4}}}}},3]$$$ and is equal to $$$(6 + 7 + 4) - (1 + 4) = 17 - 5 = 12$$$.$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation (the number $$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but the array contains $$$4$$$).

Input: The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Then follows the description of each test case.The only line of each test case description contains $$$3$$$ integers $$$n$$$, $$$x$$$, $$$y$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le x, y \le n$$$).

Output: For each test case, output a single integer — the maximum score among all permutations of length $$$n$$$.

Note: The first test case is explained in the problem statement above.In the second test case, one of the optimal permutations will be $$$[12,11,\color{blue}{\underline{\color{black}{2}}},4,8,\color{blue}{\underline{\color{red}{\underline{\color{black}{9}}}}},10,6,\color{blue}{\underline{\color{black}{1}}},5,3,\color{blue}{\underline{\color{red}{\underline{\color{black}{7}}}}}]$$$. The score of this permutation is $$$(9 + 7) - (2 + 9 + 1 + 7) = -3$$$. It can be shown that a score greater than $$$-3$$$ can not be achieved. Note that the answer to the problem can be negative.In the third test case, the score of the permutation will be $$$(p_1 + p_2 + \ldots + p_9) - p_9$$$. One of the optimal permutations for this case is $$$[9, 8, 7, 6, 5, 4, 3, 2, 1]$$$, and its score is $$$44$$$. It can be shown that a score greater than $$$44$$$ can not be achieved.In the fourth test case, $$$x = y$$$, so the score of any permutation will be $$$0$$$.

Sample Inputs:
8
7 2 3
12 6 3
9 1 9
2 2 2
100 20 50
24 4 6
1000000000 5575 25450
4 4 1

Sample Outputs:
12
-3
44
0
393
87
179179179436104
-6

Solution (Python):
""""""
import sys, math, cmath, time, collections
start_time = time.time()

def solve():
    (n, x, y) = invr()
    com = n // (x * y // math.gcd(x, y))
    nx = n // x - com
    ny = n // y - com
    sys.stdout.write(str(((n - nx + 1 + n) * nx >> 1) - ((1 + ny) * ny >> 1)) + '\n')

def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    for t in range(inp()):
        solve()
    if not ONLINE_JUDGE:
        print('Time Elapsed :', time.time() - start_time, 'seconds')
        sys.stdout.close()

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    return input().strip()

def invr():
    return map(int, input().split())
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    import io, os
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Solution (Python):
import math
ans = []
for _ in range(int(input())):
    (n, x, y) = list(map(int, input().split()))
    s = 0
    lcm = x * y // math.gcd(x, y)
    (n_pos, n_neg) = (n // x, n // y)
    n_intersect = n // lcm
    n_pos -= n_intersect
    n_neg -= n_intersect
    s += n_pos * (2 * n - n_pos + 1) // 2
    s -= n_neg * (1 + n_neg) // 2
    ans.append(s)
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
import math
sys.setrecursionlimit(100000)

def my_input():
    return sys.stdin.readline().strip()

def solve():
    (n, x, y) = map(int, my_input().split())
    cx = n // x
    cy = n // y
    c = n // (x * y // math.gcd(x, y))
    cx -= c
    cy -= c
    return cx * (n - cx) + cx * (cx + 1) // 2 - cy * (cy + 1) // 2

def main():
    print('\n'.join([str(solve()) for _ in range(int(my_input()))]))
main()