「题解」Optimal Currency Exchange

一道很有意思的数学题，第一眼没觉得有多难，结果瞎搞了一个多小时才AC，真是有趣……

一 题目

Source

Descriptions

Andrew was very excited to participate in Olympiad of Metropolises. Days flew by quickly, and Andrew is already at the airport, ready to go home. He has n rubles left, and would like to exchange them to euro and dollar bills. Andrew can mix dollar bills and euro bills in whatever way he wants. The price of one dollar is d rubles, and one euro costs e rubles.

Recall that there exist the following dollar bills: 1, 2, 5, 10, 20, 50, 100, and the following euro bills — 5, 10, 20, 50, 100, 200 (note that, in this problem we do not consider the 500 euro bill, it is hard to find such bills in the currency exchange points). Andrew can buy any combination of bills, and his goal is to minimize the total number of rubles he will have after the exchange.

Help him — write a program that given integers n, e and d, finds the minimum number of rubles Andrew can get after buying dollar and euro bills.

Input

The first line of the input contains one integer n (1≤n≤108) — the initial sum in rubles Andrew has.
The second line of the input contains one integer d (30≤d≤100) — the price of one dollar in rubles.
The third line of the input contains integer e (30≤e≤100) — the price of one euro in rubles.

Output

Output one integer — the minimum number of rubles Andrew can have after buying dollar and euro bills optimally.

---

二 题解

题目大意：你有一堆卢布，去换两种钱（美元和欧元），汇率分别是d对1和e对1。美元有1, 2, 5, 10, 20, 50, 100的面值，欧元有5, 10, 20, 50, 100, 200的面值，现在要求求出你能剩下的钱数的最小值。

首先想到的是背包，这个大概都能想出来就不多讲，写起来长这样：

for(int i=1;i<=n;i++){
    for(int j=1;j<=7;j++)
        if(i-D[j] >= 0) f[i] = max(f[i], f[i-D[j]]+D[j]);
    for(int j=1;j<=5;j++)
        if(i-E[j] >= 0) f[i] = max(f[i], f[i-E[j]]+E[j]);
}  

然后1e8的数据范围妥妥的RE了。

然后回到题目。首先观察到一个结论：对于美元来讲，所有的面值都是一美元面值的倍数啊…也就是说换美元的话，不管你换到多少张不同面值的钞票，实际上都可以看成换了一堆面值为一美元的钞票。对于欧元也同理。
那么也就是说，我们只需要考虑换成一美元和五欧元两种面值就好了。

于是把这两种钞票分别所需要的卢布的数量表示出来，不妨设x=d,y=5e。设美元换了a张，欧元换了b张，那么剩下的钱数就是n-(ax+by)。设c=n-(ax+by)，实际上就是要最小化c。

然后c=n-(ax+by)不觉得很眼熟么…移项后就是ax+by=n-c，其中x,y,n已知，可以看作关于a,b的不定方程。但是c呢？c可能有很多取值，但是不难发现，某一c值可行的条件是ax+by=n-c这个关于a,b的不定方程有a,b同为非负整数的解。

怎么判定？由裴蜀定理的推广我们知道不定方程有整解的条件是(a,b)|c，但是非负这个条件怎么保证呢？
不定方程的整数通解是：针对于某一特解(x0,y0)，( x0+i(b/(a,b)), y0-i(a/(a,b)) )是方程的通解（注意：其中i∈Z，除号后面的(a,b)实际表示gcd(a,b)）。
那么显然，若x0,y0同时⩾0，则一定有非负整数解；若x0,y0同时<0，则一定没有非负整数解，因为即使让x0,y0中的一者变得⩾0，另一者也只会越来越小。那么对于x0,y0中有一者<0，另一者⩾0的情况呢？
不妨假定x0⩾0而y0<0。我们希望让y0⩾0，于是不妨设y0+i(a/(a,b))⩾0。那么对于整数i，如果i最小时，也有x0-i(b/(a,b))<0的话，那么我们就肯定不能通过调整特解来使得解均为非负数，反之则一定可以。x0<0而y0⩾0的情况也同理。
那么实际上就是几个判断的事：

bool check(){
    ...
    int k = c/g,kx = b/g,ky = a/g;
    x = x0*k,y = y0*k;
    if(x>=0 && y>=0) return true;
    if(x<0 && y<0) return false;
    int i = 0;
    if(x < 0){
        while(x < 0) x += kx,i++; //调整特解使得x非负
        if(y-i*ky < 0) return false; //此时另一解为负，则一定无非负整数解
        return true;
    }
    while(y < 0) y += ky,i++; //反之同理
    if(x-i*kx < 0) return false;
    return true;
}

然后就好了，我们知道了如何判断一个c可行与否。不难发现有c⩽min(n mod a, n mod b)，后面那个东西不会大于100，于是枚举c就好了啊。

上面的内容用到了一点解不定方程的知识，顺手推推博：1,2。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
 
int n,a,b,r = 0;

int gcd(int a,int b) {return b?gcd(b,a%b):a;}
void exgcd(int a,int &x,int b,int &y){ //exgcd递归
    if(!b){x = 1; y = 0; return;}
    exgcd(b,x,a%b,y);
    int t = x; x = y; y = t-(a/b)*y;
}
bool ExGcd(int a,int &x,int b,int &y, int c){ //解不定方程并判断有无非负整数解
    int g = gcd(a,b);
    if(c % g) return false; //无整数解
    int x0,y0; exgcd(a,x0,b,y0); //转化为求解ax+by=gcd(a,b)
    int k = c/g,kx = b/g,ky = a/g;
    x = x0*k,y = y0*k; //得到ax+by=c的特解(x,y)
 
    //判定部分
    if(x>=0 && y>=0) return true;
    if(x<0 && y<0) return false;
    
    int i = 0;
    if(x < 0){
        while(x < 0) x += kx,i++; //调整特解使得x非负
        if(y-i*ky < 0) return false; //此时另一解为负，则一定无非负整数解
        return true;
    }
    while(y < 0) y += ky,i++; //同理
    if(x-i*kx < 0) return false;
    return true;
}
 
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    b *= 5; //乘上面值
 
    int x,y;
    while(!ExGcd(a,x,b,y,n-r)) r++; //找到最小的r
 
    printf("%d",r);
 
    return 0;
}