#include

#include

#include

#include

using namespace std;

typedef long long LL;

LL n, a, b, c, s, t;

LL extgcd(LL a, LL b, LL &x, LL &y) {

if (!b) {

x = 1; y = 0;

return a;

}

LL res = extgcd(b, a%b, x, y);

LL tmp = x;

x = y; y = tmp-a/b*y;

return res;

}

void solve(LL a, LL b, LL s, LL t, LL n) {

bool swp=0;

if (a

LL x1, y1, x2, y2;

LL d= t-s;

LL gcd1 = extgcd(a, b, x1, y1);

LL gcd2 = extgcd(n, gcd1, x2, y2);

if (-d % gcd2) {

puts("no solution");

return;

}

a /= gcd1; b /= gcd1;

n /= gcd2; gcd1 /= gcd2; d /= gcd2;

x2 *= d; y2 *= d;

LL hmr = x2/gcd1;

y2 += n*hmr;

LL ansx=0, ansy=0;

LL minsum=1LL<<62, x=x1*y2, y=y1*y2;

LL sum, dx=x1*n, dy = y1*n;

hmr = y/a;

x += b*hmr; y -= a*hmr;

hmr = dy/a;

dx += b*hmr; dy -= a*hmr;

while (1) {

if (y < 0) {

x -= b; y += a;

}

else if (y >= a) {

x += b; y -= a;

}

sum = x+y;

if (x >= 0 && (sum

ansx = x;

ansy = y;

minsum = sum;

}

if (x >= minsum) break;

x += dx; y += dy;

}

if (swp) swap(ansx, ansy);

cout<

}

int main() {

while (1) {

cin>>n;

if (n==0) break;

cin>>a>>b>>s>>t;

solve(a, b, s, t, n);

}

return 0;

}

Logo

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。

更多推荐