officeyutong

分类： 玄学

  • ZJOI2014 力

    (其实这道题应该叫强

    其实这就是一道多项式乘法

    题目大意:给出所有的$$q_i(q_i \leq 10^5)$$求$$E_i$$

    其中$$E_i=\sum_{j<i}\frac {q_j} {(j-i)^2}-\sum_{j>i}\frac {q_j} {(j-i)^2}$$

    令n=5 展开式子可得

    $$E_1=0-q_2-q_3*\frac{1}{4}-q_4*\frac{1}{9}-q_5*\frac{1}{16}$$

    $$E_2=q_1-0-q_3-q_4*\frac{1}{4}-q_5*\frac{1}{9}$$

    …(省略)

    $$E_5=q_1*\frac{1}{16}-q_2*\frac{1}{9}-q_3*\frac{1}{4}-q_4-0$$

    然后会发现 式子中的正的那几项恰好是多项式$$q_1+q_2+q_3+q_4+q_5$$与多项式$$0+1+\frac 1 4+\frac 1 9+\frac 1 {16}$$的高次前五项

    而负数部分则是$$-q_5-q_4-q_3-q_2-q_1$$与多项式$$0+1+\frac 1 4+\frac 1 9+\frac 1 {16}$$相乘的第次后五项

    然后加起来即可

    附代码

     

  • 关于二维ST表

    嗯..这种算法是我一节语文课想出来的qwq

    就是把普通的SparseTable推广到二维的情形。

    在一个矩阵中,预处理出以每一个元素为左上角的大小为$$2^0,2^1,2^2…..$$等的矩阵的最大值或最小值，查询时像普通的ST表那样拼起来就可以了

    注意的是，如果要查询的区域无法使用四个大小相同的正方形覆盖，则需要将查询的区域拆成两个区域分别查询，详情见代码。

    HAOI2007 修筑绿化带

    https://www.luogu.org/problemnew/show/P2219

     

    
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/*
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */
#p\
r\
a\
g\
m\
a GCC optimize("O2")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;

using int_t = int;
const int_t LARGE = 1000;
int_t mins[LARGE + 1][LARGE + 1][11];
int_t matrix[LARGE + 1][LARGE + 1];

int_t n, m, a, b, c, d;
int_t pow2[30];

int_t queryMin(int_t r1, int_t c1, int_t r2, int_t c2) {
    //   cout << "querying min " << r1 << " " << c1 << " " << r2 << " " << c2 << endl;
    int_t rowN = r2 - r1 + 1;
    int_t colN = c2 - c1 + 1;
    //cout << "row n =" << rowN << endl;
    //cout << "col n = " << colN << endl;
    int_t rowK = floor(log2(rowN));
    int_t colK = floor(log2((colN)));
    //cout << " k = " << k << endl;
    if (rowK > colK) {
        int_t mid = (r1 + r2) / 2;
        return min(queryMin(r1, c1, mid, c2), queryMin(mid + 1, c1, r2, c2));
    } else if (colK > rowK) {
        int_t mid = (c1 + c2) / 2;
        return min(queryMin(r1, c1, r2, mid), queryMin(r1, mid + 1, r2, c2));
    } else {
        return min(
                min(mins[r1][c1][rowK], mins[r1][c2 - pow2[rowK] + 1][rowK]),
                min(mins[r2 - pow2[rowK] + 1][c1][rowK], mins[r2 - pow2[rowK] + 1][c2 - pow2[rowK] + 1][rowK])
                );
    }
}

int_t getSum(int_t r1, int_t c1, int_t r2, int_t c2) {
    return matrix[r2][c2] + matrix[r1 - 1][c1 - 1] - matrix[r1 - 1][c2] - matrix[r2][c1 - 1];
}

int main() {
    pow2[0] = 1;
    for (int_t i = 1; i <= 29; i++) pow2[i] = pow2[i - 1]*2;
    cin >> n >> m >> a >> b >> c>>d;
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = 1; j <= m; j++) {
            cin >> matrix[i][j];
            matrix[i][j] += -matrix[i - 1][j - 1] + matrix[i][j - 1] + matrix[i - 1][j];
        }
    }
    //枚举出所有的小矩阵
    for (int_t i = 1; i + c - 1 <= n; i++) {
        for (int_t j = 1; j + d - 1 <= m; j++) {
            mins[i][j][0] = getSum(i, j, i + c - 1, j + d - 1);
        }
    }
    for (int_t k = 1; pow2[k] <= min(n - 1, m - 1); k++) {
        for (int_t row = 1; row + pow2[k] + c - 1 <= n; row++) {
            for (int_t col = 1; col + pow2[k] + d - 1 <= m; col++) {
                mins[row][col][k] = min(
                        min(mins[row][col][k - 1], mins[row + pow2[k - 1]][col][k - 1]),
                        min(mins[row][col + pow2[k - 1]][k - 1], mins[row + pow2[k - 1]][col + pow2[k - 1]][k - 1])
                        );
            }
        }
    }
    int_t result = 0;
    for (int_t i = 1; i + a - 1 <= n; i++) {
        for (int_t j = 1; j + b - 1 <= m; j++) {
            int_t x = queryMin(i + 1, j + 1, i + a - 1 - 1 - (c) + 1, j + b - 1 - 1 - (d) + 1);
            result = max(result, getSum(i, j, i + a - 1, j + b - 1) - x);
        }

    }
    cout << result;
    return 0;

}

    HAOI2007 理想的正方形
    https://www.luogu.org/problemnew/show/2216

    // luogu-judger-enable-o2
// luogu-judger-enable-o2

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/*
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */
#p\
r\
a\
g\
m\
a GCC optimize("O2")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;

using int_t = int;
const int_t LARGE = 1000;
int_t mins[LARGE + 1][LARGE + 1][11];
int_t maxs[LARGE + 1][LARGE + 1][11];
int_t a, b, n;
int_t pow2[30];

int_t queryMax(int_t r1, int_t c1, int_t r2, int_t c2) {
    int_t rowN = r2 - r1 + 1;
    int_t colN = c2 - c1 + 1;
    int_t k = floor(log2(min(rowN, colN)));
    if (rowN > pow2[k + 1]) {
        int_t mid = (r1 + r2) / 2;
        return max(queryMax(r1, c1, mid, c2), queryMax(mid + 1, c1, r2, c2));
    } else if (colN > pow2[k + 1]) {
        int_t mid = (c1 + c2) / 2;
        return max(queryMax(r1, c1, r2, mid), queryMax(r1, mid + 1, r2, c2));
    } else {
        return max(
                max(maxs[r1][c1][k], maxs[r1][c2 - pow2[k] + 1][k]),
                max(maxs[r2 - pow2[k] + 1][c1][k], maxs[r2 - pow2[k] + 1][c2 - pow2[k] + 1][k])
                );
    }
}

int_t queryMin(int_t r1, int_t c1, int_t r2, int_t c2) {
    //   cout << "querying min " << r1 << " " << c1 << " " << r2 << " " << c2 << endl;
    int_t rowN = r2 - r1 + 1;
    int_t colN = c2 - c1 + 1;
    //cout << "row n =" << rowN << endl;
    //cout << "col n = " << colN << endl;
    int_t k = floor(log2(min(rowN, colN)));
    //cout << " k = " << k << endl;
    if (rowN > pow2[k + 1]) {
        int_t mid = (r1 + r2) / 2;
        return min(queryMin(r1, c1, mid, c2), queryMin(mid + 1, c1, r2, c2));
    } else if (colN > pow2[k + 1]) {
        int_t mid = (c1 + c2) / 2;
        return min(queryMin(r1, c1, r2, mid), queryMin(r1, mid + 1, r2, c2));
    } else {
        return min(
                //         cout << " " << mins[r1][c1][k] << " " << mins[r1][c2 - pow2[k] + 1][k] << " " << mins[r1 - pow2[k] + 1][c1][k] << " "
                min(mins[r1][c1][k], mins[r1][c2 - pow2[k] + 1][k]),
                min(mins[r2 - pow2[k] + 1][c1][k], mins[r2 - pow2[k] + 1][c2 - pow2[k] + 1][k])
                );
    }
}

int main() {
    pow2[0] = 1;
    for (int_t i = 1; i <= 29; i++) pow2[i] = pow2[i - 1]*2;
    cin >> a >> b>>n;
    for (int_t i = 1; i <= a; i++) {
        for (int_t j = 1; j <= b; j++) {
            cin >> mins[i][j][0];
            maxs[i][j][0] = mins[i][j][0];
        }
    }
    for (int_t k = 1; pow2[k] <= min(a, b); k++) {
        for (int_t row = 1; row + pow2[k] - 1 <= a; row++) {
            for (int_t col = 1; col + pow2[k] - 1 <= b; col++) {
                mins[row][col][k] = min(
                        min(mins[row][col][k - 1], mins[row + pow2[k - 1]][col][k - 1]),
                        min(mins[row][col + pow2[k - 1]][k - 1], mins[row + pow2[k - 1]][col + pow2[k - 1]][k - 1])
                        );
                maxs[row][col][k] = max(
                        max(maxs[row][col][k - 1], maxs[row + pow2[k - 1]][col][k - 1]),
                        max(maxs[row][col + pow2[k - 1]][k - 1], maxs[row + pow2[k - 1]][col + pow2[k - 1]][k - 1])
                        );
            }
        }
    }
    int_t result = 0x7fffffff;
    for (int_t i = 1; i + n - 1 <= a; i++) {
        for (int_t j = 1; j + n - 1 <= b; j++) {
            result = min(result, queryMax(i, j, i + n - 1, j + n - 1) - queryMin(i, j, i + n - 1, j + n - 1));
        }
    }
    cout << result << endl;
    return 0;
}

  • splay树基本思路

    对区间[begin,end]进行修改:

    1.先将l-1旋转到根，然后将r+1旋转到根的右子节点，这是root->rightChd->leftChd所代表的子树就包括了[begin,end]的所有元素

    给区间[begin,end]添加一个值:先执行操作1 然后给root->rightChd->leftChd的标记上加上要添加的值,并且把root->rightChd->leftChd的值加上要加的值，然后再每次进行旋转时将某个点的标记下传

    查询:每个点设置一个值,表示以该节点为根的子树的总和,并且在执行旋转时维护

    区间翻转待添加

    区间删除: 执行操作1 然后删掉root->rightChd->leftChd即可

    区间插入:首先把要插入的区间构建成一棵BST 然后把要插入的位置

  • 关于可持久化线段树的一些体会

    这个玩意我搞了一个月 终于在jzw dalao的指引下成功的搞懂了qwq

    说一下几点注意事项

    1.如果写指针版,那么最好使用定位new运算符从预分配的栈空间上分配内存(new 从heap里分配内存比较耗时)

    2.代表一个节点的结构体里 没用的东西尽量别写(可持久化数据结构十分耗内存)

    注意c++的对象内存对齐

    3.查找区间第k小时 设当前节点为node 如果k<=node->leftChd->value 那么就从node->leftChd里查找第k小 直到找到叶子结点

    如果k>node->leftChd->value  就从node->rightChd里查找第k-node->leftChd->value

    代码:https://www.luogu.org/problemnew/show/3834

     

    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/* 
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */
#p\
r\
a\
g\
m\
a GCC optimize("O3")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG
using namespace std;

using int_t = int;
const int_t LARGE = 200000;
const int_t INF = 0x7ffffff;

struct Node {
    int_t begin = 0;
    int_t end = 0;
    int_t value = 0;
    Node* leftChd = nullptr;
    Node* rightChd = nullptr;
};
Node* roots[LARGE + 1];

char buff[sizeof (Node)*1000000 * 7];
const int_t LENGTH = sizeof (buff) / sizeof (Node);
int_t used = 0;

Node* nextNewNode() {
    if (used < LENGTH) {
        return new (buff + (used++) * sizeof (Node)) Node;
    } else {
        return new Node;
        
    }
}
int_t data[LARGE + 1];

struct Num {
    int_t val;
    int_t id;
} nums[LARGE + 1];

Node* buildTree(int_t left, int_t right) {
    Node* node = nextNewNode();
    node->begin = left;
    node->end = right;
    if (left == right) {
        node->value = 0;
    } else {
        int_t mid = (left + right) / 2;
        node->leftChd = buildTree(left, mid);
        node->rightChd = buildTree(mid + 1, right);
        node->value = node->leftChd->value + node->rightChd->value;
    }
    return node;
}

void buildNextTree(Node*& node, int_t pos, Node* x) {
    node = nextNewNode();
    node->begin = x->begin;
    node->end = x->end;
    if (node->begin == node->end && node->begin == pos) {
        node->value = x->value + 1;
    } else if (pos >= node->begin && pos <= node->end) {
        buildNextTree(node->leftChd, pos, x->leftChd);
        buildNextTree(node->rightChd, pos, x->rightChd);
        node->value = node->leftChd->value + node->rightChd->value;
    } else {
        node = x;
    }
}

int_t query(int_t begin, int_t end, int_t k) {
    Node* leftPtr = roots[begin - 1];
    Node* rightPtr = roots[end];
    while (leftPtr->begin != leftPtr->end) {
        int_t leftSize = rightPtr->leftChd->value - leftPtr->leftChd->value;
        if (k <= leftSize) {
            leftPtr = leftPtr->leftChd;
            rightPtr = rightPtr->leftChd;
        } else {
            k -= (rightPtr->leftChd->value - leftPtr->leftChd->value);
            leftPtr = leftPtr->rightChd;
            rightPtr = rightPtr->rightChd;
        }
    }
    return leftPtr->begin;
}
int_t orders[LARGE + 1];

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    int_t n, m;
    cin >> n>>m;
    for (int_t i = 1; i <= n; i++) {
        cin >> nums[i].val;
        nums[i].id = i;
    }
    sort(&nums[1], &nums[n + 1], [&](Num & x, Num & y)->bool {
        return x.val < y.val;
    });
    for (int_t i = 1; i <= n; i++) orders[nums[i].id] = i;
    roots[0] = buildTree(1, n);
    for (int_t i = 1; i <= n; i++) {
        buildNextTree(roots[i], orders[i], roots[i - 1]);
    }
    for (int_t i = 1; i <= m; i++) {
        int_t left, right, k;
        cin >> left >> right>>k;
        //   cout << "query " << left << " " << right << " " << k << " = " << query(left, right, k) << endl;
        cout << nums[query(left, right, k)].val << endl;
    }
    return 0;
}

  • AC自动机模板

    我在这里卡了一个周了，终于写出来了qwq

     当走到一个节点时，一定要沿着失配路径走，一直走到根节点，因为失配路径所经过的节点已定能匹配到！

    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年12月3日, 下午7:11
 */
#pra\
gma GCC optimize("O3")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
using int_t = long long int;
using std::string;
using std::cout;
using std::endl;
using std::strlen;
using std::cin;
using std::queue;
using std::vector;
using std::ifstream;
using std::max;

enum MemoryType {
    preAllocation, dynamicAllocation
};

struct Node {
    Node* children[26];
    int_t id = 0;
    Node* fail = nullptr;
    //标明这个节点是如何分配内存的
    MemoryType type = MemoryType::preAllocation;
//当前节点的某个子节点是否在构建失配路径前就已经存在
    bool raw[26];

    inline Node* &getChild(char chr) {
        return children[chr - 'a'];
    }
};
int_t used;
//预分配一块内存，用来加快程序分配内存的速度
char memPool[sizeof (Node)*20000 + 1];
const int_t size = sizeof (memPool) / sizeof (Node);
Node* root = nullptr;
char buff[1000000 + 10];
char patterns[200][100];
int_t result[200];
//获取一个新的Node
Node* nextNewNode() {
    if (used < size) //预分配的内存还有空位的情况下 直接使用定位new在预分配的内存中分一个Node return new(memPool + (used++) * sizeof (Node)) Node; else { //否则就用new在堆里分配内存 Node* x = new Node; memset(x->children, 0, sizeof (x->children));
        memset(x->raw, 1, sizeof (x->raw));
        x->type = MemoryType::dynamicAllocation;
        return x;
    }
}
//将字符串插入到Trie
inline void insert(const char * str, int_t id) {
    int_t length = strlen(str);
    Node* ptr = root;
    for (int_t i = 0; i < length; i++) {
        //    cout << i << endl;
        //    if (i % 10 == 0) cout << i << endl; if (ptr->getChild(str[i]) == nullptr) {
            ptr->getChild(str[i]) = nextNewNode();
        }
        ptr = ptr->getChild(str[i]);
    }
    ptr->id = id;

}
//构建失配路径
inline void buildUpFailPtrs() {
    queue<Node* > qu;
    for (char chr = 'a'; chr <= 'z'; chr++) { //根节点所有子节点的失配路径指向根 if (root->getChild(chr)) {
            root->getChild(chr)->fail = root;
            qu.push(root->getChild(chr));
        }
    }
    while (qu.empty() == false) {
        Node* front = qu.front();
        qu.pop();
        for (char chr = 'a'; chr <= 'z'; chr++) { Node* & chd = front->getChild(chr);
            if (chd == nullptr) {
                //如果一个节点不存在 那么就补上这条路径 可降低匹配函数中的代码量
                chd = front->fail->getChild(chr);
                front->raw[chr - 'a'] = false;
            } else {
                Node* fail = front->fail;
                while (fail && (fail->getChild(chr) == nullptr)) {
                    fail = fail->fail;
                }
                if (fail == nullptr) fail = root;
                chd->fail = fail->getChild(chr);
                if (chd->fail == nullptr) chd->fail = root;
                qu.push(chd);
            }
        }
    }
}

inline void match(char * str) {
    memset(result, 0, sizeof (result));
    int_t length = strlen(str);
    Node* ptr = root;
    for (int_t i = 0; i < length; i++) {
        //  if (i % 10 == 0) cout << i << endl; ptr = ptr->getChild(str[i]);
        //        cout << "moving to " << ptr << " with str " << str[i] << endl; if (ptr == nullptr) { ptr = root; continue; } Node* temp = ptr; //重要！！！一定要沿着当前节点的失配路径已知往回走，因为这些失配路径上的字符串一定匹配到了！！ while (temp) { // if(temp->id==0) break;
            if (temp->id) {
                //    cout << "found " << patterns[temp->id] << " at pos " << i;
                //       cout << "result " << temp->id << " from " << result[temp->id] << " to " << result[temp->id] + 1 << endl; result[temp->id]++;
            }

            temp = temp->fail;
        }

    }

}
//删掉树
void remove(Node* r) {
    if (r == nullptr) return;
    for (char chr = 'a'; chr <= 'z'; chr++) { if (r->raw[chr - 'a'])
            remove(r->getChild(chr));
    }
    //只有某个节点是使用堆分配的内存时才能delete
    //定位new不能用delete
    if (r->type == MemoryType::dynamicAllocation)
        delete r;
}

int main() {
    int_t n;
    while (true) {
        remove(root);
        memset(memPool, 0, sizeof (memPool));
        used = 0;
        cin>>n;
        if (n == 0) break;

        root = nextNewNode();
        for (int_t i = 1; i <= n; i++) { cin >> patterns[i];
            insert(patterns[i], i);
        }
        buildUpFailPtrs();
        cin>>buff;
        match(buff);
        int_t maxTime = 0;
        for (int_t i = 1; i <= n; i++) {
            maxTime = max(maxTime, result[i]);
        }
        cout << maxTime << endl;
        for (int_t i = 1; i <= n; i++) {
            if (result[i] == maxTime) {
                cout << patterns[i] << endl;
            }
        }
    }
    return 0;
}

  • 乘法逆元

    如果$$ax\equiv 1(mod n)$$则称x为a模n意义下的逆

    则有$$ax-ny=1$$，然后用扩展欧几里得算法求解即可。

  • 欧拉函数

    设函数$$\phi (x)$$为不超过x且与x互素的正整数的个数(两个数互素，则两个数的最大公因数为1)

    则$$\phi(x)=x(1-\frac {1} {p_1})(1-\frac {1} {p_2})(1-\frac {1} {p_3})(1-\frac {1} {p_4})·····(1-\frac {1} {p_n})$$

    其中$$p_n$$为将x通过唯一分解定理所得的式子的底数，即$$n={p_1}^{k_1} {p_2}^{k_2} {p_3}^{k_3} {p_4}^{k_4} …..{p_m}^{k_m} $$ 其中$$p_n$$为素数

     

    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = long long int;

int_t func(int_t x) {
    int_t result = x;
    for (int_t i = 2; i <= x; i++) {
        //如果x的可以整除i,则结果中i的指数+1
        if (x % i == 0) {
            //    result = result * (i - 1) / i;
            //先乘后除防止溢出
            result = result / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) result = result / x * (x - 1);
    return result;
}

int main() {
    int_t x;
    while (cin >> x) {
        int_t result = func(x);
        cout<

    或者可以通过类似于线性筛素数的方式求出一定范围内所有的数的欧拉函数值
    

    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
using int_t = long long int;
const int_t MAX = 100000;
int_t phi[MAX + 1];
int main() {
    int_t x;
    cin>>x;
    memset(phi, 0, sizeof (phi));
    phi[1] = 1;
    for (int_t i = 2; i <= x; i++) {
        if (phi[i] == 0) {
            for (int_t j = i; j <= x; j = j + i) {
                if (phi[j] == 0) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }

    }
    for(int_t i=1;i<=x;i++) cout<<"phi("<<i<<") = "<<phi[i]<<endl;

}

  • 欧几里得算法与扩展欧几里得算法

    欧几里得算法，即人教版高中数学必修三上的辗转相除法

    用于求两个整数的最大公因数(即gcd(a,b))
    注:a b的最小公倍数等于$$\frac {ab}{\gcd \left(a,b\right)}$$

    int gcd(int a, int b) {
    //边界b==0 此时a就是结果
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

    扩展欧几里得算法:在求最大公约数的同时求出方程$$ax+by=gcd(a,b)$$的一组整数解，使|x|+|y|最小

    //a b 方程中的a b 
//gcd 用来存放gcd(a,b)
//x y 用来存放解
void exgcd(int a, int b, int & gcd, int& x, int& y) {
    //边界b==0 此时a就是结果
    if (b == 0) {
        x = 1;
        y = 0;
        gcd = a;
    } else {
        exgcd(b, a % b, gcd, y, x);
        y -= (a / b) * x;

    }
}

    求出$$ax+by=gcd(a,b)$$的解之后,如果$$c$$可以整除$$gcd(a,b)$$ 就说明方程$$ax+by=c$$存在整数解$$x_0,y_0$$，而且这组解为$$x_1=x_0*c/gcd(a,b),y_1=y_0*c/gcd(a,b)$$

    然后，如果$$x_1,y_1$$是方程$$ax+by=c$$的解,则$$x_1+k*a/gcd(a,b),y_1-k*b/gcd(a,b)$$都是方程$$ax+by=c$$的解