买不到的数目（python）

第四届省赛a组

题目的意思是让我们求解ax+by=z，这个式子能在0到a*b之间，有哪些解

因为a和b互质，所以当z大于a*b时，一定有解

其实有一个式子专门求这个 ：a*b-a-b

import math

a,b=map(int,input().split())
if math.gcd(a,b)==1:
    print(a*b-a-b)

直接就可以ac

当然可以用dp做

也可以直接寄，时空复杂度都一样

import math

a,b=map(int,input().split())
count=0
ans=[]
if math.gcd(a,b)==1:
    for i in range(a+1):
        for j in range(b+1):
            if a*j+b*i<=a*b:
                ans.append(a*j+b*i)

    ans=sorted(ans,reverse=True)
 
    i=0
    while True:
        if i1:
                print(ans[i]-1)
                break
        i+=1

数论太难了，扩展欧几里得 扩展中国剩余 不会用啊