px+qy类问题

已知GCD（p,q)=1,p>=1,q>=1,求不能表示为px+qy(x,y>=0)的最大数

https://www.zybang.com/question/b95cb4f0c50f64517cc747c2dde2ec99.html?ssl=1

x>=0,y>=0很重要. 1. 假设可以表示为pq-q-p 那么 px+qy=pq-q-p p(x+1)+q(y+1)=pq p|y+1,q|x+1 又p(x+1),q(y+1)=0故pq-q-p,就无法表示成px+qy 2. (p-1)(q-1)=pq-p-q+1 对于n>pq-q-p即n>=(q-1)(p-1) gcd(p,q)=1 对于z0>b,显然a>0 那么如果a>q,取a1=a-q,b1=b+p 那么有a1*p+b1*q=z. 如果a1>q,可以继续以得到 Ap+Bq=z,且0