ACM – UVA571 – 模方程 -

一开始在扩展gcd上想了许久没有办法将得出的数字直接转换成为相应的输出，后来发现就是模方程。

因为不求最佳解，所以直接使用ca*x = n (mod cb)即可。这个方程的解可以覆盖全部的n，因为该方程如果有解，则n是gcd(ca, cb)的倍数。因为ca, cb互质 gcd (ca, cb) = 1，所以明显通过单纯的加满B，向A中倒，然后清空A就可以遍历所有n的解（尽管可能不是最佳解）。

不能是cb*x = n (mod ca)，因为n可能大于ca.

如果求最佳解，显然是bfs。当然这到题目也可以dfs来做，不过明显要复杂很多。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int ca, cb, n;
    while(scanf("%d%d%d", &ca, &cb, &n) != EOF)
    {
        //解模方程 ax = n(mod b)
        int a = , b = ;
        while(b != n)
        {
            if(a == )
            {
                puts("fill A");
                a = ca;
            }
            if(b == cb)
            {
                puts("empty B");
                b = ;
            }
            if(a > cb - b)
            {
                a = a - (cb-b);
                b = cb;
            }
            else
            {
                b += a;
                a = ;
            }
            puts("pour A B");
        }
        puts("success");
    }
    return ;
}