//디오판토스 방정식은 ax+by = c 형태의 방정식을 말함. 여기서 a,b,c는 상수이고
//x,y가 구하려는 값 (방정식의 모든 값은 정수여야 함!!)
//디오판토스 방정식은 확장 유클리드 알고리즘으로 효율적으로 풀 수 있음
//디오판토스 방정식의 해가 존재하는 경우와 c가 gcd(a,b)로 나누어떨어지는 경우는 동치
//따라서 ax+by=gcd(a,b)로 풀고 나누어떨어지므로 c/gcd(a,b)값만큼 값들에 곱해주면 답
//디오판토스 방정식의 해는 유한하지 않음(무한)
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
 
public class Lecture 
{
	public static void Main(string[] args) {
        //39x+15y = 12로 가정
        (int x, int y, int g) = Gcd(39, 15);
        int k = 12/g;
        Console.WriteLine($"x = {x*k}, y = {y*k}");
    }
 
    //확장 유클리드 알고리즘
    public static (int,int,int) Gcd(int a, int b){
        if(b == 0) return (1,0,a);
        else{
            int x, y, g;
            (x,y,g) = Gcd(b, a%b);
            return (y, x-(a/b)*y, g);
        }
    }
}

Ly/rlJTsmKTtjJDthqDsiqQg67Cp7KCV7Iud7J2AIGF4K2J5ID0gYyDtmJXtg5zsnZgg67Cp7KCV7Iud7J2EIOunkO2VqC4g7Jes6riw7IScIGEsYixj64qUIOyDgeyImOydtOqzoAovL3gseeqwgCDqtaztlZjroKTripQg6rCSICjrsKnsoJXsi53snZgg66qo65OgIOqwkuydgCDsoJXsiJjsl6zslbwg7ZWoISEpCi8v65SU7Jik7YyQ7Yag7IqkIOuwqeygleyLneydgCDtmZXsnqUg7Jyg7YG066as65OcIOyVjOqzoOumrOymmOycvOuhnCDtmqjsnKjsoIHsnLzroZwg7ZKAIOyImCDsnojsnYwKLy/rlJTsmKTtjJDthqDsiqQg67Cp7KCV7Iud7J2YIO2VtOqwgCDsobTsnqztlZjripQg6rK97Jqw7JmAIGPqsIAgZ2NkKGEsYinroZwg64KY64iE7Ja065ao7Ja07KeA64qUIOqyveyasOuKlCDrj5nsuZgKLy/rlLDrnbzshJwgYXgrYnk9Z2NkKGEsYinroZwg7ZKA6rOgIOuCmOuIhOyWtOuWqOyWtOyngOuvgOuhnCBjL2djZChhLGIp6rCS66eM7YG8IOqwkuuTpOyXkCDqs7HtlbTso7zrqbQg64u1Ci8v65SU7Jik7YyQ7Yag7IqkIOuwqeygleyLneydmCDtlbTripQg7Jyg7ZWc7ZWY7KeAIOyViuydjCjrrLTtlZwpCnVzaW5nIFN5c3RlbTsKdXNpbmcgU3lzdGVtLklPOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpwdWJsaWMgY2xhc3MgTGVjdHVyZSAKewoJcHVibGljIHN0YXRpYyB2b2lkIE1haW4oc3RyaW5nW10gYXJncykgewogICAgICAgIC8vMzl4KzE1eSA9IDEy66GcIOqwgOyglQogICAgICAgIChpbnQgeCwgaW50IHksIGludCBnKSA9IEdjZCgzOSwgMTUpOwogICAgICAgIGludCBrID0gMTIvZzsKICAgICAgICBDb25zb2xlLldyaXRlTGluZSgkInggPSB7eCprfSwgeSA9IHt5Kmt9Iik7CiAgICB9CgogICAgLy/tmZXsnqUg7Jyg7YG066as65OcIOyVjOqzoOumrOymmAogICAgcHVibGljIHN0YXRpYyAoaW50LGludCxpbnQpIEdjZChpbnQgYSwgaW50IGIpewogICAgICAgIGlmKGIgPT0gMCkgcmV0dXJuICgxLDAsYSk7CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgaW50IHgsIHksIGc7CiAgICAgICAgICAgICh4LHksZykgPSBHY2QoYiwgYSViKTsKICAgICAgICAgICAgcmV0dXJuICh5LCB4LShhL2IpKnksIGcpOwogICAgICAgIH0KICAgIH0KfQ==