[9094번] 수학적 호기심

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학적 지식

이 문제에서는 

(a2+b2+m)/(ab)가 정수가 되기 위한 조건을 묻고 있다.

필자는 처음에 (a2+b2+m)/(ab)식이 float형일때와 int형일때 같다면

즉, 소수점이 존재하지 않는다면 같다고 생각하고 문제에 접근했다.

물론 맞는 말이다.

하지만, 다른 분들의 코드를 봤더니

(a2+b2+m)/(ab)가 정수가 되기 위한 조건은 (a2+b2+m)/(ab) = n이라고 생각해볼 때,

(a2+b2+m) = (ab)*n이다. 즉, (a2+b2+m) % (ab)가 0이면 정수인 것이었다.

이 문제는 따라서 두가지 방법으로 접근이 된다.

실제로 /를 하여 소수점이 발생하는지 확인하는 방법과, %를 이용하여 나누어 떨어지는지 확인하는 것이다.

소스 코드 : 

< float, int를 이용하는 방법 >

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    int a, b;
    int cnt = 0;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
 
        for (float x = 1; x < a; x++)
            for (float y = x + 1; y < a; y++)
                    (float)((x*x + y*y + b) / (x*y)) == (int)((x*x + y*y + b) / (x*y)) ? cnt++ : 0;
 
        cout << cnt << endl;
        cnt = 0;
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

< %를 이용하는 방법 >

#include <stdio.h>
int main()
{
    int t;
    scanf("%d", &t);
    for(int z= 0; z < t; z++)
    {
        int n,m;
        scanf("%d %d", &n, &m);
        int count = 0;
        for(int b = 2; b < n; b++)
        {
            for(int a = 1; a < b; a++)
            {
                if((a*a+b*b+m)%(a*b)==0)
                    count++;
            }
        }
        printf("%d\n", count);
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>