class="markdown_views prism-kimbie-light">

单变元模线性方程

目标 :
已知 a, b, n 求x
使得 ax ≡ b(mod n)
令 d = gcd(a,n)
先使用扩展欧几里得求 ax + ny = d 的解,如果 b 不能整除 d 则无解,否则 mod n 意义下的解有d 个,可以对某个解不断的加n/d得到.
下面代码调用了欧几里得函数 输入 a,b,c
输出 所有从零到n中满足 ax ≡ b(mod n) 的解 vector lme(long long a,long long b,long long n) { long long x,y; long long d = gcd(a,n,x,y); vector ans; ans.clear() if(b % d == 0) { x %= n; x += n; x %= n; ans.pish_back(x*(b/d) % (n/d)); for(long long i = 1; i < d; ++i) ans.push_back((ans[0] + i * n / d) % n); } return ans; } 使用见 POJ 2115 .cpp