[BOJ 9497] 피라미드 수열

https://www.acmicpc.net/problem/9497

9497번: 피라미드 수열

 

- 문제 요약

 

높이가 H인 피라미드 수열은 1, 2, ..., H-1, H, H-1, ..., 2, 1, 2, ... 이다. 즉, 앞의 원소 2H-2개가 무한히 반복해서 나타난다.

두 자연수 N과 M이 주어졌을 때, 높이가 N인 피라미드 수열과 높이가 M인 피라미드 수열의 각 원소를 순서쌍으로 만든다. 이때, 나오는 순서쌍 종류의 개수를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

서로 다른 순서쌍 (i, j)의 갯수를 세는 문제입니다.

이 문제를 2차원 평면 상에서 (i-1, j-1) 좌표의 개수를 세는 문제로 바꿔서 문제를 해결할 수 있습니다. (gcd 사용)

 

 

- 코드 작성

 

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

typedef long long ll;
ll n,m,g,a,b;

ll gcd(ll x,ll y){
	if(y==0){
		return x;
	}
	else{
		return gcd(y,x%y);
	}
}

int main(){ 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	g=gcd(n-1,m-1);
	a=(n-1)/g;
	b=(m-1)/g;
	cout<<(a+1)*(b+1)/2+a*b*(g-1);
}

코드 제출 결과