拡張ユークリッド互除法

[tipstar0125]

一次不定方程式ax+by=cにおいて、x,yが整数解をもつ ⇔cはgcd(a,b)の倍数

参考：https://qiita.com/sysdev/items/92f24243c399c503fa45

def gcd(a,b):
    while b!=0:
        r=a%b
        a,b=b,r
    return abs(a)

def ext_gcd(a,b):
    # a*x+b*y=c
    x1,y1,c1=1,0,a
    x2,y2,c2=0,1,b

    while c2!=0:
        q=c1//c2
        c1,c2=c2,c1-c2*q
        x1,x2=x2,x1-x2*q
        y1,y2=y2,y1-y2*q
    if c1<0:
        c1=-c1
        x1,y1=-x1,-y1
    return (c1,x1,y1)

a=2022
b=1224
g,x,y=ext_gcd(a,b)

# a*x+b*y=gcd(a,b)
print(a*x+b*y==g)

[tipstar0125]

問題：https://atcoder.jp/contests/abc340/tasks/abc340_f 解答：https://atcoder.jp/contests/abc340/submissions/50262913

def ext_gcd(a,b):
    # a*x+b*y=c
    x1,y1,c1=1,0,a
    x2,y2,c2=0,1,b

    while c2!=0:
        q=c1//c2
        c1,c2=c2,c1-c2*q
        x1,x2=x2,x1-x2*q
        y1,y2=y2,y1-y2*q
    if c1<0:
        c1=-c1
        x1,y1=-x1,-y1
    return (c1,x1,y1)

x,y=map(int,input().split())
# |a*y-b*x|=2
# a*y+b*(-x)=+/-2を満たす整数解a,bを求める
# 上式において、a,bが整数解をもつには、+/-2がgcd(y,-x)の倍数であること
# つまり、gcd(y,-x)が1 or 2のとき(gcdは正)
# 下記より、a,b,gcdを拡張ユークリッド互除法で求める
# a*y+b*(-x)=gcd(y,-x)
# 右辺が2になるように、a,bを調整
g,x,y=ext_gcd(y,-x)
if g>2:print(-1)
else:print(2*x//g,2*y//g)