• 洛谷P4549 裴蜀定理模板


    裴蜀定理:

    若给出参数 a , b , c a,b,c a,b,c,不定方程 a x + b y = c ax+by=c ax+by=c有解的充要条件是
    g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)c

    证明:

    g c d ( a , b ) gcd(a,b) gcd(a,b)显然是 a x ax ax的一个因子,也是 b y by by的一个因子,所以 a x + b y ax+by ax+by的含义为 g c d ( a , b ) gcd(a,b) gcd(a,b)的两个倍数相加,结果一定还是 g c d ( a , b ) gcd(a,b) gcd(a,b)的倍数,所以只需要 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)c,方程就有解

    同样的原理,可以扩展至任意个数的参数:

    给出 n n n个参数 a i a_{i} ai c c c,使方程
    ∑ i = 1 n a i x i = c \sum_{i=1}^{n}a_{i}x_{i}=c i=1naixi=c
    有解的充要条件是
    g c d ( a 1 , a 2 , . . . , a n ) ∣ c gcd(a_{1},a_{2},...,a_{n})|c gcd(a1,a2,...,an)c

    例题:洛谷 P 4549 P4549 P4549

    题意:

    给出 n n n个参数 a i a_{i} ai,求另一个整数序列 x i x_{i} xi,使得
    S = ∑ i = 1 n a i x i S=\sum_{i=1}^{n}a_{i}x_{i} S=i=1naixi
    满足 S > 0 S>0 S>0,且 S S S最小

    Solution:

    显然右式是一个不定方程,那么 S S S要存在取值就只可能是 g c d ( a 1 , a 2 , . . . , a n ) gcd(a_{1},a_{2},...,a_{n}) gcd(a1,a2,...,an),这个就是答案了。不过 a i a_{i} ai可能是负的,只需要取负 a i a_{i} ai在计算就可以保证是正的了

    // #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    
    using ll=long long;
    using ull=unsigned long long;
    const int N=2e5+5,inf=0x3fffffff;
    const long long INF=0x3fffffffffffffff,mod=1e9+9;
    
    int main()
    {
        #ifdef stdjudge
            freopen("in.txt","r",stdin);
        #endif
        int ans,n; cin>>n>>ans;
        if(ans<0) ans=-ans;
        while(--n)
        {
            int x; cin>>x;
            if(x<0) x=-x;
            ans=__gcd(ans,x);
        }     
        cout<<ans;
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
  • 相关阅读:
    【五分钟Paper】基于参数化动作空间的强化学习
    C++课堂整理--第一章内容
    房地产渠道风控怎么开展
    探索工业AI智能摄像机的高端科技
    Figma 插件学习(一)
    【Prism系列】Prism中的命令
    社区团购小程序开发
    TS —— TS的基础知识点
    【多线程】进程与线程
    linux安装mysql
  • 原文地址:https://blog.csdn.net/stdforces/article/details/127827070