[코드포스] 1872 D. Plus Minus Permutation

 

📖 Solution

 

문제의 요구사항을 정리해보면 길이 n의 조합중에서 x배수의 숫자의 합에서 y배수의 숫자의 합의 차를 가장 크게 만들 수 있는 조합을 찾고 그 차를 출력하는 문제이다.  

 

A - B의 차를 크게 만들기 위해서는 A를 최대한 크게, B를 최대한 작게 만들면 된다. 그렇다면 x의 배수 위치에는 n부터 내림차순으로 배치하고, y의 배수 위치에는 1부터 오름차순으로 배치하면 된다. 

 

둘이 겹치는 부분이 있을 수 있는데 이는 0이 되기 때문에 상관없다.

 

그렇다면 이제 구해야 하는 점은 n에서 x 배수의 갯수, y 배수의 갯수 그리고 겹치는 부분이다. 이 겹치는 부분은 lcm 을 사용하여 찾을 수 있다.

 

💻 Code

import sys, math
input = sys.stdin.readline
 
def sigma(a,b):
    return (b*(b+1))//2 - (a*(a-1))//2 
 
t = int(input())  
for _ in range(t):
    n,x,y = map(int, input().split())
 
    comm = n//math.lcm(x,y)
    x_cnt = n//x - comm
    y_cnt = n//y - comm
    print(sigma(n-x_cnt+1, n)-sigma(1, y_cnt))

 

 

🔗 Problem  https://codeforces.com/contest/1872/problem/D

Problem - D - Codeforces