求解形如ax+by == n (a,b已知)的方程的非负整数解个数时，需要用到扩展欧几里得定理，先求出最小的x的值，然后通过处理剩下的区间长度即可得到答案。
放出模板：
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a,b) * b;
}
ll extend_gcd(ll a,ll b,ll&x,ll&y) {
if(!b) {
x = ;
y = ;
return a;
}
ll xt = , yt = ;
ll d = extend_gcd(b, a % b, xt, yt);
x = yt;
y = xt - yt * (a/b);
return d;
}
ll cal(ll a,ll b,ll n) { //计算ax+by == n的非负整数解组数
ll x = ,y = ,d;
d = extend_gcd(a,b,x,y);
if(n % d != ) {
return ;
}
x *= n / d, y *= n / d;
ll LCM = lcm(a,b);
ll t1 = LCM / a, t2 = LCM / b;
if(x<) {
ll num = (-x) / t1;
x += num * t1;
y -= num * t2;
if(x<) {
y -= t2;
x += t1;
}
}
if(y<) {
ll num = (-y) / t2;
y += num * t2;
x -= num * t1;
if(y<) {
y += t2;
x -= t1;
}
}
ll ans = x > && y > ;
if(ans) {
ans += min((x-) / t1, ((n-) / b - y) / t2);
ans += min((y-) / t2, ((n-) / a - x) / t1);
}
return ans;
}