中国余数定理(Chinese Remainder Theorem

前言

---

中国余数定理也叫孙子定理记录在《孙子算经》中：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”

关于孙子算经这道题的解法宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知。

即：先找到5与7公倍数中余3为1的数=70，3与7公倍数中余5为1的数=21，3与5公倍数中余7为1的数=15，然后将70 * 2(除以3余2)+21 * 3(除以5余3)+15 * 2(除以7余2)=233，最后233%(3 * 5 * 7=105)=23。

接下来记录一道用到中国余数定理的题目。

题目(来源GCJ2019 1A Golf Gophers)

---

Problem

Last year, a bunch of pesky gophers took up residence in our orchard. We tried to change our line of work by opening up a miniature golf course, but it looks like the gophers have followed us here! Once again, we need to figure out how many gophers there are, but we cannot observe them directly because they are secretive and nocturnal, whereas we like to sleep at night. We do know there are between 1 and M gophers, inclusive.

Our mini golf course is famous for having a small electronic windmill on each of its 18 holes. The i-th windmill has 2 ≤ B_i ≤ 18 blades, which are numbered from 0 to B_i-1, clockwise. Each night, before going to sleep, we turn off the windmills and set each one such that blade 0 is pointing downward, which is important so that the windmills can charge up properly for the next day. However, we have noticed that when we wake up, the windmills have been disturbed. Since our mini golf course is in a windless area, we think the mischievous gophers must be responsible!

We know that every night, all of the gophers emerge, one by one; each of them chooses one of the windmills independently and uniformly at random and rotates it counterclockwise by one blade. So, for example, for a windmill with 3 blades for which 0 is pointing downward, the first gopher to interact with it turns it so that 1 is pointing downward, and then the next gophers to interact with that windmill make the downward-pointing blade have number 2, then 0, then 1, and so on.

We have devised a plan. We designed our windmills so that we can easily change the number of blades (to modulate the difficulty of our course), and we will now take advantage of this! Each night, before going to sleep, we can choose the number of blades on each of the 18 windmills, within the given limits; we do not have to use the same number of blades on each windmill, or make the same choices every night. In the morning, we will observe the number on each windmill's downward-pointing blade.

We have N nights in which to figure out G, the number of gophers. Can you help us?

Input and output

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing three integers T, N and M, the number of test cases, the number of nights allowed per test case and the maximum number of gophers, respectively. Then, you need to process T test cases.

In each test case, your program processes up to N + 1 exchanges with our judge. You may make up to N exchanges of the following form:

• Your program outputs one line with eighteen integers between 2 and 18, inclusive; the i-th of these represents the number of blades you want the i-th windmill to have on that night.
• The judge responds with one line with eighteen integers; the i-th of these represents the number on the downward-pointing blade of the i-th windmill in the morning, after the gophers have worked their mischief. If you sent invalid data (e.g., a number out of range, or a malformed line), the judge instead responds with -1.

On each night, for each gopher, the choice of which windmill the gopher turns is uniform at (pseudo)-random, and independent of any other choice by any gopher (including itself) on any night.

After making between 0 and N exchanges as explained above, you must make one more exchange of the following form:

• Your program outputs one integer: your guess for G, the number of gophers.
• The judge responds with one line with a single integer: 1 if your answer is correct, and -1 if it is not (or you have provided a malformed line).

After the judge sends -1 to your input stream (because of either invalid data or an incorrect answer), it will not send any other output. If your program continues to wait for the judge after receiving -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

Limits

1 ≤ T ≤ 20.
Time limit: 20 seconds per test set.
Memory limit: 1GB.

Test set 1 (Visible)

N = 365.
M = 100.

Test set 2 (Hidden)

N = 7.
M = 10⁶.

Testing Tool

You can use this testing tool to test locally or on our servers. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the Interactive Problems section of the FAQ.

Local Testing Tool

To better facilitate local testing, we provide you the following script. Instructions are included inside. You are encouraged to add more test cases for better testing. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.

If your code passes the testing tool but fails the real judge, please check the Coding section of our FAQ to make sure that you are using the same compiler as us.

Download testing_tool.py

Sample Interaction

This interaction corresponds to Test set 1. Suppose that, unbeknownst to us, the judge has decided that there are 10 gophers.

  t, n, m = readline_int_list()   // Reads 20 into t, 365 into n and 100 into m.
  // Choose numbers of blades for day 1.
  printline 2 2 2 2 18 3 3 3 3 3 3 4 4 4 4 5 2 2 to stdout
  flush stdout
  // Reads 0 0 0 0 0 0 1 2 1 0 1 2 0 0 0 0 1 0 into res.
  res = readline_int_list()
  // Choose numbers of blades for day 2.
  printline 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 to stdout
  flush stdout
  // Reads 0 1 1 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 into res.
  res = readline_int_list()
  printline 8 to stdout        // We make a wrong guess even though we could
  flush stdout                 // have investigated for up to 363 more nights.
  verdict = readline_int()     // Reads -1 into verdict (judge has decided our
                               //   solution is incorrect)
  exit                         // Exits to avoid an ambiguous TLE error

Notice that even though the guess was consistent with the information we received from the judge, we were still wrong because we did not find the correct value.

分析

---

题目大意是有一群囊鼠晚上出来活动，他们会拨乱我们放置的风车叶子，并且是顺时针拨乱的比如有三片标记的叶子0，1，2。一只囊鼠通过由0 ~> 1，两只囊鼠通过就0 ~> 1 ~> 2，3只就0 ~> 1 ~> 2 ~> 0，（其实就是通过囊鼠个数求叶子的余数）。并且囊鼠每晚只完全随机选择一个风车来拨动，下面希望在有限次设置风车下计算出囊鼠数量，风车数量固定18，每个风车叶子可以选择[2,18]中的任意值，并且初始都是叶子都是标记0。

首先，我们可以确定我们不能每晚风车选不同数值，像Sample Interaction一样，这样完全随机的返回18个余数无法利用。我们只能每晚所有风车选一样的叶子数。比如18个18，如果运气好（囊鼠数量很少或者很多个夜晚的话），我们有可能18个风车都没有经历一个轮回，那么所有返回数值相加就是结果。

但是很不幸，对于大数据囊鼠达到10⁶，只有7个夜晚是不可能完成的。这就需要用到中国余数定理来解决了。

这里和孙子算经中的问题有点不同，余数数量达到了7个，但是并不影响解法原理，只需从3个余数扩展到7个。比如扩展到（3，5，7，9）四个数，对与3的余数处理，我同样找到5 * 7 * 9的公倍数中余3为1的数，然后乘以3的余数，最后把4个操作数加起来余3 * 5 * 7 * 9的值就得到结果。

然后回到题目中我们需要7个数的乘积>10⁶就能保证最后值能覆盖10⁶所有可能。这里选择得是{5,7,9,11,13,16,17}这7个数，当然也可以选择其他乘积更大的数，比如11到17。

最后在求多个数乘积和某个数余1的数的时候可以用到扩展欧几里德算法，公式ax=1(mod p)，p是我们的选定的某个叶子数，a是其他数乘积，通过扩展欧几里德算法可以求得x（也叫乘法逆元），ax就是我们要的余p为1的值。这里不能用费马小定理的原因是我们选择的数当中9，16都不是素数。

解法代码

---

//
//  main.cpp
//  Golf Gophers
//
//  Created by Jiao Liu on 4/22/19.
//  Copyright © 2019 ChangHong. All rights reserved.
//

#include <iostream>

using namespace std;
int t,n,m;
int blade[7] = {5,7,9,11,13,16,17};
int tot = 5*7*9*11*13*16*17;

long long Extend_Gcd(long long a, long long b, int &x, int &y) {
    if (!b) {
        x = 1; y = 0;
        return  a;
    }
    else {
        long long r = Extend_Gcd(b, a%b, y, x);
        y -= a / b*x;
        return r;
    }
}

int main(int argc, const char * argv[]) {
    cin>>t>>n>>m;
    while (t--) {
        long long ans = 0;
        for (int d = 0; d < min(7, n); d++) {
            for (int i = 0; i < 18; i++) {
                cout<<blade[d]<<" ";
            }
            cout<<endl;
            fflush(stdout);
            long long total = 0;
            for (int i = 0; i < 18; i++) {
                int tm;
                cin>>tm;
                total += tm;
            }
            int p = tot/blade[d];
            int x,y;
            Extend_Gcd(p, blade[d], x, y);
            ans += x * total * p;
            ans %= tot;
        }
        cout<<ans%tot<<endl;
        fflush(stdout);
        int res;
        cin>>res;
        if (res != 1) {
            return 0;
        }
    }
    return 0;
}