挑战程序竞赛系列（41）：4.1中国剩余定理
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434705
挑战程序竞赛系列（41）：4.1中国剩余定理
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 1006: Biorhythms
今天学习了下中国剩余定理，很多参考资料啊，推荐博文：
http://blog.csdn.net/acdreamers/article/details/8050018
其他的可看可不看，简单来说，中国剩余定理是用来求解同余方程组的，比如
x≡1mod5x≡2mod6x≡3mod7
x \equiv 1 \mod 5 \ x \equiv 2 \mod 6 \ x \equiv 3 \mod 7 \
中国剩余定理指出，如果给出的每个方程模数两两互素，就能通过一种方法计算出来，具体方法可以参考《初等数论及其应用》。
在这里给出书上的证明：
该证明还是很好理解的，主要还是通过两两互素的性质构造一个联立解，最后证明联立解符合每个方程即可，给人一种凑答案的过程，此解法如何想到令人深思。
具体做法如下：
好了，有了这些知识，第一题能解了，无非把上述思想用代码实现一遍。
代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201708/P1006.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
void solve() {
int t = 0;
while (true){
int p = ni();
int e = ni();
int i = ni();
int d = ni();
if (p == -1 && e == -1 && i == -1 && d == -1) break;
int[] a = new int[3];
int[] m = new int[3];
a[0] = p;
a[1] = e;
a[2] = i;
m[0] = 23;
m[1] = 28;
m[2] = 33;
int ans = CRT(a, m, 3);
if (ans <= d){
ans += 21252;
}
out.println("Case " + (++t) + ": the next triple peak occurs in " + (ans - d) + " days.");
}
}
class Pair{
int d;
int x;
int y;
public Pair(int d, int x, int y){
this.d = d;
this.x = x;
this.y = y;
}
}
public Pair extgcd(int a, int b){
if (b == 0){
return new Pair(a, 1, 0);
}
else{
Pair p = extgcd(b, a % b);
Pair ans = new Pair(0, 0, 0);
ans.d = p.d;
ans.x = p.y;
ans.y = p.x - (a / b) * p.y;
return ans;
}
}
public int mod_inverse(int a, int m){
Pair p = extgcd(a, m);
if (p.d != 1) return -1;
return (p.x % m + m) % m;
}
public int CRT(int[] a, int[] m, int n){
int M = 1;
int ans = 0;
for (int i = 0; i < n; ++i){
M *= m[i];
}
for (int i = 0; i < n; ++i){
int inv = mod_inverse(M / m[i], m[i]);
ans += a[i] * M / m[i] * inv;
ans %= M;
}
return ans;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}POJ 2891: Strange Way to Express Integers
嘿，中国剩余定理表明同余方程组两两互素的情况下可解，那么遇到模数不互素的情况该如何？
参考博文：http://www.cnblogs.com/MashiroSky/p/5918158.html
此篇讲的还是比较详细的，尤其这文字解释令人一下豁然开朗，我就不重复劳动力了。
但个人总觉得吧，这和中国剩余定理没啥关系了吧，难道这种解法也是孙子发明的？
大致思路是对所有同余方程两两合并，在合并的过程中可以求出新的一个特解和它的一个解集，解集用新的同余方程表示（这想法相当漂亮），那么该解集就能慢慢适应所有同余方程了。
最终在解集中找寻一个最小的即可，上述两篇博文有C++的具体实现，Java版本的就自己补上吧。
代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201708/P2891.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
void solve() {
while (more()){
int n = ni();
long[] a = new long[n];
long[] m = new long[n];
for (int i = 0; i < n; ++i){
m[i] = ni();
a[i] = ni();
}
out.println(CRT(a, m, n));
}
}
class GCD{
long d;
long x;
long y;
public GCD(long d, long x, long y){
this.d = d;
this.x = x;
this.y = y;
}
}
public long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}
public GCD extgcd(long a, long b){
if (b == 0) return new GCD(a, 1, 0);
else{
GCD g = extgcd(b, a % b);
GCD ans = new GCD(0, 0, 0);
ans.d = g.d;
ans.x = g.y;
ans.y = g.x - (a / b) * g.y;
return ans;
}
}
public long mod_inverse(long a, long m){
GCD g = extgcd(a, m);
if (g.d != 1) return -1;
return (g.x % m + m) % m;
}
class LL{
long val;
public LL(){}
public LL(long val){
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public boolean merge(long a1, long m1, long a2, long m2, LL a3, LL m3){
GCD g = extgcd(m1, m2);
long c = a2 - a1;
long d = g.d;
if (c % d != 0) return false;
m1 /= d;
m2 /= d;
c /= d;
long inv = mod_inverse(m1, m2);
c *= inv;
c %= m2;
c *= m1 * d;
c += a1;
m3.val = m1 * m2 * d;
a3.val = c;
return true;
}
public long CRT(long[] a, long[] m, int n){
long a1 = a[0];
long m1 = m[0];
for (int i = 1; i < n; ++i){
long a2 = a[i];
long m2 = m[i];
LL a3 = new LL();
LL m3 = new LL();
if (!merge(a1, m1, a2, m2, a3, m3)) return -1;
a1 = a3.val;
m1 = m3.val;
}
return (a1 % m1 + m1) % m1;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}POJ 3708: Recurrent Function
此题对数学的要求较高，还是有一定难度的，用到的知识点也较多，简单说说我的心路历程吧。
就拿式子：
f(d×n+j)=d×f(n)+bj
f (d \times n + j) = d \times f(n) + b_j
你能想到什么？它实际上是一种m转d进制，这是思维上的突破，想到这点后续都简单了。
我们可以把递推式化为最终的表达式如下：
f(m)=ap1⋅dn−1+∑i=2n(bpi⋅dn−i),ap1ϵ[1，d）,(bpiϵ[0,d),iϵ2,n)
f(m) = a_{p_1} \cdot d ^{n - 1} + \sum_{i=2}^n( {b_{p_i}}\cdot d ^{n - i}) , a_{p_1}\epsilon[1，d）, (b_{p_i}\epsilon[0, d),i\epsilon2, n)
如果递推式难以理解的话，你可以想象10进制转d进制的一个过程，因为递推式其实模拟的就是这个过程，并且在转换的过程当中，余数一一对应到了bjb_j上了。
当然你也可以参考《具体数学》P16，它也介绍了一些，此处推荐博文：
http://www.hankcs.com/program/algorithm/poj-3708-recurrent-function.html
但代码量相对冗长，比较难懂。
好了，m转成d进制，对应的值f(m)=(ap1bp2...bpn)df(m) = (a_{p_1}b_{p_2}...b_{p_n})_d
所以第一步判断m和k转到d进制后，位数是否相等，不相等则无解。
接着，我们要考虑m中每一位的变化了， 因为经过一次f映射，实际上是从set中找一个数置换，而set中的值是有限个数，且在[1, d)之间，那么必然在置换过程中会存在循环的情况，那么自然的就考虑m中的每一位经过多少次能将mim_i置换到kik_i上去。
这样就可以列出一系列的同余方程了。
此处可以参考博文：
http://blog.csdn.net/adjky/article/details/60583393
思路很清楚，代码很精简。
代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201708/P3708.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
int[] A;
int[] B;
void solve() {
while (true){
int N = ni();
if (N == -1) break;
A = new int[N];
B = new int[N];
for (int i = 1; i < N; ++i){
A[i] = ni();
}
for (int i = 0; i < N; ++i){
B[i] = ni();
}
String m = ns();
String k = ns();
int[] nm = new int[m.length() + 16];
for (int i = m.length() - 1; i >= 0; --i) nm[i] = m.charAt(i) - '0';
int[] nk = new int[k.length() + 16];
for (int i = k.length() - 1; i >= 0; --i) nk[i] = k.charAt(i) - '0';
LEN_M = tran(nm, m.length(), M, N);
LEN_K = tran(nk, k.length(), K, N);
//radix(m, k, N);
if (LEN_M != LEN_K) out.println("NO");
else{
getRC(LEN_M);
boolean valid = true;
for (int i = 0; i < LEN_M; ++i){
if (C[i] == -1){
valid = false;
break;
}
}
if (!valid) out.println("NO");
else{
long ans = CRT(C, R, LEN_M);
if (ans == -1) out.println("NO");
else{
out.println(ans);
}
}
}
}
}
/********************欧几里德两两合并***************************/
class GCD{
long d;
long x;
long y;
public GCD(long d, long x, long y){
this.d = d;
this.x = x;
this.y = y;
}
}
public long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}
public GCD extgcd(long a, long b){
if (b == 0) return new GCD(a, 1, 0);
else{
GCD g = extgcd(b, a % b);
GCD ans = new GCD(0, 0, 0);
ans.d = g.d;
ans.x = g.y;
ans.y = g.x - (a / b) * g.y;
return ans;
}
}
public long mod_inverse(long a, long m){
GCD g = extgcd(a, m);
if (g.d != 1) return -1;
return (g.x % m + m) % m;
}
class LL{
long val;
public LL(){}
public LL(long val){
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public boolean merge(long a1, long m1, long a2, long m2, LL a3, LL m3){
GCD g = extgcd(m1, m2);
long c = a2 - a1;
long d = g.d;
if (c % d != 0) return false;
m1 /= d;
m2 /= d;
c /= d;
long inv = mod_inverse(m1, m2);
c *= inv;
c %= m2;
c *= m1 * d;
c += a1;
m3.val = m1 * m2 * d;
a3.val = c;
return true;
}
public long CRT(int[] a, int[] m, int n){
long a1 = a[0];
long m1 = m[0];
for (int i = 1; i < n; ++i){
long a2 = a[i];
long m2 = m[i];
LL a3 = new LL();
LL m3 = new LL();
if (!merge(a1, m1, a2, m2, a3, m3)) return -1;
a1 = a3.val;
m1 = m3.val;
}
return (a1 % m1 + m1) % m1;
}
/****************大数进制转换****************/
int MAX_D = 500 + 16;
int[] M = new int[MAX_D];
int[] K = new int[MAX_D];
int LEN_M;
int LEN_K;
public int tran(int ten[], int len, int ans[], int d){
int cnt = 0;
int tcnt = 0;
while(tcnt < len){
for(int i = tcnt; i < len; ++i){
ten[i + 1] += (ten[i] % d) * 10;
ten[i] /= d;
}/**模拟除法,余数 * 10存在ten[len]中*/
ans[cnt++] = ten[len] / 10;
ten[len] = 0;
while(ten[tcnt] == 0 && tcnt < len) ++tcnt;
}
return cnt;
}
/***************************计算每一位的模数****************************/
int[] R = new int[MAX_D];
int[] C = new int[MAX_D];
// 获得模数
public void getRC(int len){
Arrays.fill(C, -1);
int id = len - 1;
R[id] = 1;
int cnt = 0;
if (M[id] == K[id]) C[id] = 0;
for (int i = A[M[id]]; i != M[id]; i = A[i]){
++R[id];
++cnt;
if (i == K[id]) C[id] = cnt;
}
for (int i = 0; i < id; ++i){
if (K[i] == M[i]) C[i] = 0;
R[i] = 1;
cnt = 0;
for (int j = B[M[i]]; j != M[i]; j = B[j]){
++R[i];
++cnt;
if (K[i] == j) C[i] = cnt;
}
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}注意m和k是大数，用字符串去取，且需要用大数高精度转d进制的做法，才能AC。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月30日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录