有哪些做短租的网站好,互联网服务网站建设目的,创意设计产业包括哪些,制作网站教程Water(扩欧求特解与通解) 题意#xff1a;给容量分别为A与B的水杯#xff0c;问确切喝到C水的最小操作次数 有4种操作#xff1a;选一杯全喝#xff0c;选一杯全部倒掉#xff0c;选一杯装满#xff0c;将一杯的水尽量倒到另一杯中 思路#xff1a;只有AxByC有解时才能确…Water(扩欧求特解与通解) 题意给容量分别为A与B的水杯问确切喝到C水的最小操作次数 有4种操作选一杯全喝选一杯全部倒掉选一杯装满将一杯的水尽量倒到另一杯中 思路只有AxByC有解时才能确切喝到X水 裴蜀定理如果a、b是整数那么一定存在整数x、y使得axbyk*gcd(a,b)。 思路要求xy的特解可以使用exgcd的板子令c k * gcd(A, B)则Ax By c;exgcd求出来的是k 1时的特解 只要将x * c / gcd(A, B) y * c / gcd(A, B)此时x和y就是方程Ax By c的特解 这里有一个步长的概念对于x他的步长是 B / gcd(A, B) 对于y他的步长是 A / gcd(A, B) 要求最小整数解只需要把x除上他的步长就能知道x要走多少步才能最接近0再把x - 步长 * 步数就可以让x最接近0然 后在对原点附近的 (xt⋅步长,y−t⋅步长)求min即可得到最小整数解
#includebits/stdc.h
using namespace std;#define endl \n
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
typedef pairint, int pr;#define int long long
#define ll long long
#define fr(i,l,r) for(int il;ir;i)
#define ufr(i,n,z) for(int i n;i z; i--)
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se secondconst int N 1e6 10;
const int mod 998244353, inf LONG_LONG_MAX;
int dx[] { 0,0,-1,0,1 }, dy[] { 0,-1,0,1,0 };
int n, m;int a[N];
int gcd(int a, int b) { //辗转相除return !b ? a : gcd(b, a % b);
}
int exgcd(int a, int b, int x, int y) //扩欧板子
{if (b 0) {x 1; y 0;return a; //到达递归边界开始向上一层返回}ll d exgcd(b, a % b, y, x);y - (a / b) * x;return d;
}
void solve()
{int a, b, c;cin a b c;if (c % gcd(a, b) ! 0) {cout -1 \n; //无解}else {int x, y;int d exgcd(a, b, x, y);x * c / d; y * c / d; //特解(除去最大公约数乘上C)int dx b / d; int dy a / d;y (x / dx) * dy;x - (x / dx) * dx; //最小整数解只需要把x除上他的步长就能知道x要走多少步才能最接近0int ans inf;fr(i, -10, 10) {int xx x dx * i; int yy y - dy * i; //通解ans min(ans, max((xx yy) 1, (abs(xx - yy) 1) - 1));}cout ans \n;}
}signed main()
{// ios;int t 1;cin t;while (t--) solve();return 0;
} P1082 [NOIP2012 提高组] 同余方程 题意:求ax-1(mod b)的最小整数解输入数据保证一定有解。 转变为ax1by,移项ax-by1,
扩欧求的特解x/d,y/d,
通解x/d-i*(x/d/b/d)*b/d-x/d-x/b*(b/d)-x/d-i*x/d
#includeiostream
#define int long long
using namespace std;
int exgcd(int a, int b, int x, int y) {if (b 0) {x 1, y 0;return a;}int d exgcd(b, a % b, y, x);y - (a / b) * x;return d;
}
signed main(){int a, b;int x, y;cin a b;exgcd(a, b, x, y);cout (x % b b) % b \n;return 0;
}
