小凯的疑惑ios
题目背景：spa
NOIP2017 D1T1code
分析：结论 or 扩展欧几里得ci
正解答案就是x * y - x - y，能够用剩余系比较简单的证实，然而我用了扩欧来写，而后今天花了一段时间来证实他是等价的。下面来说讲我本身的结论证实。string
首先由于能够构造出的每个数，都应该是形如ax + by的形式，那么要将ax + by变成ax + by + 1实际上就是减小一些x变成y，或者是减小一些y，变成x，那么我能够用扩欧得到知足条件的最小的ax - by = 1, cy - dx = 1, a, b, c, d均可以很方便的求得。而后咱们就能够发现咱们每一次的+1操做应该都是经过将by变成ax，或者dx变成cy来达成，那么最大的不能实现加一操做的数应该就是(b - 1)y + (d - 1)x，因此(b - 1)y + (d - 1)x + 1是必定不能表出的，那么如何证实这必定是最大的，咱们考虑证实(b - 1)y + (d - 1)x + 2是必定可以被表出的，观察上面得到的等式ax - by = 1, dx - cy = -1, 那么(a + d)x = (b + c)y，显然a < y, b < x, d < y, c < x，(x, y) = 1，那么a + d = y, b + c = x，下面咱们来证实一个结论，存在a >= y / 2, 且b >= x / 2, 或者d >= y / 2, 且c >= x / 2。咱们不妨设x > y，a >= d，假设结论不成立，则必然存在a > y / 2，b < x / 2，稍做放缩能够得到，a >= (y + 1) / 2，b <= (x - 1) / 2，代入等式ax = by + 1，那么ax >= (xy + x) / 2，by + 1 <= (xy - y) / 2 + 1，那么xy + x <= xy - y + 2，x + y <= 2，由于原题数据在正整数范畴，只有1,1知足条件，可是数据保证存在这么一个值，因此1,1不是可行数据，因此结论在本题数据的范畴下是成立的，考虑这个结论有什么意义。若是要获得+2的操做，只能经过2by转移到2ax，或者经过2dx转移到2cy，由于，存在上述结论，若是知足的是a，b那么说明2 * b >= x，且2 * a >= y，那么咱们就能够经过(2b - x) * y转移到(2a - y) * x，由于2 * b < x + b的，那么2 * b - x < b，同理2 * a - y < a，因此必定能够达成+2的转移，到此，得证(b - 1)y + (d - 1)x + 1为最大的不可行数，而后咱们来证实上面等式与x * y - x - y等价，考虑(a + d)x = xy = by + 1 + dx，因此(b - 1)y + (d - 1)x + 1 = xy - x - y，得证。(感受评论区会有一群骂我zz的人······)it
Sourceio
/*
created by scarlyw
*/
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
long long a, b, x1, x2, x, y, a1, a2, temp;
inline void ext_gcd(long long a, long long b) {
if (b == 0) x = 1, y = 0;
else ext_gcd(b, a % b), temp = x, x = y, y = temp - a / b * y;
}
inline void solve() {
std::cin >> a >> b;
if (a == 1 || b == 1) std::cout << 0, exit(0);
ext_gcd(a, b), x1 = (x % b + b) % b, a1 = (a * x1 - 1) / b - 1;
ext_gcd(b, a), x2 = (x % a + a) % a, a2 = (b * x2 - 1) / a - 1;
std::cout << a1 * b + a2 * a + 1;
}
int main() {
// freopen("math.in", "r", stdin);
// freopen("math.out", "w", stdout);
solve();
return 0;
}