[BOJ 4563] 리벤지 오브 피타고라스

- 문제 요약

 

A^2 + B^2 = C^2

피타고라스 정리에서 A(2<=A<2^20)가 주어졌을 때, 빗변의 길이 C가 자연수인 직각삼각형을 만드는 자연수 B(B>A)의 개수를 구하시오.

(입력은 여러 개의 테스트케이스로 이루어져 있으며, 입력의 마지막 줄에는 0이 하나 주어진다.)

 

 

- 알고리즘 정리

 

피타고라스 정리 수식을 변형해서 문제를 해결할 수 있습니다.

 

A^2 + B^2 = C^2

A^2 = C^2 - B^2 = (C+B)(C-B) = x * y

(A^2의 약수에서 조건 설정 후 걸러내기)

 

 

- 코드 작성

 

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

typedef long long ll;
int result;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	while(true){
		ll a;
		cin>>a;
		if(a==0){
			return 0;
		}
		result=0;
		ll powa=pow(a,2);
		for(ll i=1;i<=a-1;i++){
			if(powa%i==0){
				ll w=powa/i-i;
				if(w%2==0 && w/2>a){
					result++;
				}
			}
		}
		cout<<result<<endl;
	}
}

코드 제출 결과