본문 바로가기
Computer Science

디오판토스 방정식

by OKOK 2019. 2. 10.

1.  디오판토스 방정식

2.  풀이를 봐도 모르겠음

3.  패쓰~


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
int dp[1000][2];
int main()
{
    freopen("input.txt", "r", stdin);
    int t, n, m, tn, a, b, c, i, on, kk;
    scanf("%d", &tn);
    for (t = 1; t <= tn; t++)
    {
        scanf("%d %d %d", &n, &m, &kk);
        on = 0;
        if (n>m);
        else
        {
            c = n;
            n = m;
            m = c;
            on = 1;
        }
        a = n;
        b = m;
        c = n % m;
        i = 2;
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
        while (1)
        {
            if (i == 2)
            {
                a = n;
                b = m;
                c = n % m;
            }
            else
            {
                a = b;
                b = c;
                c = a % b;
            }
            dp[i][0] = dp[i - 2][0] - dp[i - 1][0] * (a / b);
            dp[i][1] = dp[i - 2][1] - dp[i - 1][1] * (a / b);
            if (c == 1)
            {
                break;
            }
            i++;
        }
        printf("#%d ", t);
        if (on == 0)printf("%d %d\n", dp[i][0] * kk, dp[i][1] * kk);
        if (on == 1)printf("%d %d\n", dp[i][1] * kk, dp[i][0] * kk);
    }
}
cs

 


저작자표시

'Computer Science' 카테고리의 다른 글

흘러라 시간! 딴 짓 하기  (0) 2019.02.11
초등학생  (0) 2019.02.10
키 순서  (0) 2019.02.10
지구 온난화  (0) 2019.02.10
올해의 조련사  (0) 2019.02.10

관련글

댓글

티스토리툴바