Comments Off on 数论 - 裴枢定理初探

参考教程： 裴蜀定理 - OI Wiki (oi-wiki.org)

内容：

设a,b是不全为零的整数，则存在整数x,y使得\(ax+by=gcd(a,b)\)。

例题：

Problem - D - Codeforces

传送门： Problem - D - Codeforces

题意：

思路：

裴蜀定理，dp。

参考题解： (6条消息) D. Fox And Jumping（dp，裴蜀定理）_H-w-H的博客-****博客

只有在若干个\(l_i\)中加减法凑出1来，才能走光所有的点。

如果\(gcd(a,b)=1\),则必存在\(x,y\)，使得\(ax+by=1\)。

问题转换为如何以最小代价拼凑出gcd=1。

变成了一维dp。\(dp_i\)代表gcd为i时所需的最小代价。

由于i不连续，可以非常大，所以用map维护。

//https://codeforces.com/contest/510/problem/D
#include <bits/stdc++.h>
#define int long long
const int N = 3e2+10;
std::pair<int,int>a[N];
std::map<int,int>dp;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a; }
signed main() {
    std::ios::sync_with_stdio(false);
    int n;std::cin>>n;
    for(int i=1;i<=n;i++)std::cin>>a[i].first;
    for(int i=1;i<=n;i++)std::cin>>a[i].second;
    for(int i=1;i<=n;i++){
        dp[a[i].first]=dp[a[i].first]?std::min(dp[a[i].first],a[i].second):a[i].second;
        for(auto it:dp){
            int k = gcd(it.first,a[i].first);
            dp[k]=dp[k]?std::min(dp[k],dp[it.first]+a[i].second):dp[it.first]+a[i].second;
        }
    }
    std::cout<<(dp[1]?dp[1]:-1)<<std::endl;
}