gcd的辗转相除法
实现:
1 2 3 4 ll gcd (ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
或者直接使用
1 2 3 #include <algorithm> __gcd();
辗转相除法复杂度在O ( log max ( a , b ) ) O(\log \max(a, b)) O ( log max ( a , b ) )
扩展欧几里德算法
先了解同余方程a × x ≡ b ( m o d m ) a\times x≡b(\mod m) a × x ≡ b ( m o d m ) ,该方程等价于a × x = b + m × k a\times x=b+m\times k a × x = b + m × k
可化为a × x + b × y = c a\times x+b\times y=c a × x + b × y = c 的形式
先看"求整数x,y使a × x + b × y = 1 a\times x+b\times y=1 a × x + b × y = 1 ",显然gcd(a,b)=1,才能保证有解。事实上,一定存在(x,y)使a × x + b × y = g c d ( x , y ) a\times x+b\times y=gcd(x,y) a × x + b × y = g c d ( x , y )
模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ll extgcd (ll a, ll b, ll &x, ll &y) { ll d = a; if (b != 0 ) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1 ; y = 0 ; } return d; }
细想其实是道思维+extgcd的模板题
设t为跳跃次数
( n − m ) × t ≡ x − y ( m o d L ) (n-m)\times t≡x-y(\mod L) ( n − m ) × t ≡ x − y ( m o d L )
所以( n − m ) × t + k × L = x − y (n-m)\times t+ k\times L=x-y ( n − m ) × t + k × L = x − y
令n − m = a , L = b , x − y = c n - m = a,L = b,x - y = c n − m = a , L = b , x − y = c
则化为a x + b y = c ax + by = c a x + b y = c
又已知a x 0 + b y 0 = g c d ( a , b ) ax_0+by_0=gcd(a,b) a x 0 + b y 0 = g c d ( a , b ) 中x 0 x_0 x 0 是一个解
式子两边同乘c g \frac{c}{g} g c
得到a c x 0 g + b c y 0 g = c a\frac{cx_0}{g}+b\frac{cy_0}{g}=c a g c x 0 + b g c y 0 = c
x = c x 0 g x=\frac{cx_0}{g} x = g c x 0 就是ax+by=c的一个解
k是一个随机整数;gcd是gcd(a,b);则有公式
x = c x 0 g x 0 + ( b / g c d ) k x=\frac{cx_0}{g}x_0 + (b/gcd)k x = g c x 0 x 0 + ( b / g c d ) k
y = c x 0 g y 0 − ( a / g c d ) k y=\frac{cx_0}{g}y_0 - (a /gcd)k y = g c x 0 y 0 − ( a / g c d ) k
把(b/gcd)k通过取余除去即可得到最小解,这里注意正负
1 2 3 4 5 x = x * c / gcd; int t = b / gcd;x = (x % t + t) % t; printf ("%lld\n" , x);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <bitset> #include <string> #include <cmath> #include <sstream> using namespace std ; typedef long long ll;const double pi = acos (-1.0 );const int eps = 1e-10 ;const int mod = 1e9 + 7 ;const int INF = 0x3f3f3f3f ;const int maxn = 1005 ;ll read () { ll x = 0 ,f = 1 ; char ch = getchar(); while (ch < '0' || ch > '9' ) { if (ch == '-' ) f = -1 ; ch = getchar(); } while (ch >= '0' && ch <= '9' ) { x = x * 10 + ch - '0' ; ch = getchar(); } return x * f; } ll extgcd (ll a, ll b, ll &x, ll &y) { ll d = a; if (b != 0 ) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1 ; y = 0 ; } return d; } ll a, b, c, x, y; int main () { ll m, n, gcd, L; while (~scanf ("%lld%lld%lld%lld%lld" , &x, &y, &m, &n, &L)) { a = m - n; b = L; c = y - x; if (a < 0 ) { a = -a; c = -c; } gcd = extgcd(a, b, x, y); if (c % gcd != 0 ) puts ("Impossible" ); else { x = x * c / gcd; int t = b / gcd; x = (x % t + t) % t; printf ("%lld\n" , x); } } return 0 ; }