裴属定理

裴属定理

裴属定理，又叫贝祖定理。是一个关于最大公约数的定理。其内容为：设a,b是不全为0的整数，存在整数解(x,y)，使得ax + by = gcd(a, b)。
那么对于方程ax + by = c，若不满足[gcd(a,b)|c]，则方程无解。

扩展欧几里得定理是用来解该方程的。

题目

CF512B Fox And Jumping

题意是给定n组数(l_i,c_i)，在一个无限大的直线上，每选定一组数，你需要付出c_i的代价，以后你可以无限次向前或向后走l_i步，也可以走之前已经选过的数，问可以到达直线上任意一点的最小代价。无解输出-1。

分析：先考虑两个数a，b，如果要满足题意条件，必须使得这两个数通过数次相加或者相减使得其结果绝对值为1，也就是说ax + by = 1需要有解，再根据裴属定理，a和b必须满足条件gcd(a,b)=1才会有解。那么推广到n个数的情况，其实就是从中选出一些数来，使得其最大公约数为1，求最小代价。

这是一个背包问题，设mp[i]为最小公约数为i时的最小代价，并初始化mp[0] = 0，然后每加入一个数，就考虑更新mp中的所有值，最后输出mp[1]即可。

#include <bits/stdc++.h>

using namespace std;

map<int, int> mp;

int gcd(int a, int b) {
    return b==0?a:gcd(b, a%b);
}
int n;
int l[303], c[303];
int main() {
    cin >> n;
    for (int i=1; i<=n; i++)    cin >> l[i];
    for (int i=1; i<=n; i++)    cin >> c[i];
    map<int, int>::iterator it;
    mp[0] = 0;
    for (int i=1; i<=n; i++) {
        for (it=mp.begin(); it!=mp.end(); it++) {        //拿出一个最大公约数
            int tmp = it->first;
            int d = gcd(tmp, l[i]);
            if (mp.count(d))    mp[d] = min(mp[d], it->second + c[i]);      // 若d已经存在，考虑更新其最优解
            else    mp[d] = it->second + c[i];        // 若d不存在，那么就赋值
        }
    }
    if (mp.count(1))    cout << mp[1];
    else    cout << "-1";
    return 0;
}