首页 > 其他分享 >多元一次方程的解(扩欧 + 构造)

多元一次方程的解(扩欧 + 构造)

时间:2023-07-13 14:23:11浏览次数:60  
标签:一次方程 gcd 多元 序列 include 扩欧 define

例题:SGU 140

题意:

给出一个长度为 n 的非负整数序列 A 和两个数 P,B ,要求找出同样的非负整数序列 X 满足:
\(A_1 * X_1 + A_2*X_2 + ... + A_n*X_n = B (mod P)\)

思路:

看起来是一个多元一次方程,我们只需要找到一个合法的非负整数序列 作为解即可,所以我们可以构造答案。我们可以求出二元一次方程的解,因此我们可以从前往后,两个数就可以找到一组解,这样两两合并即可得到一组合法的解。
即:先考虑\(A_1 * X_1 + A_2*X_2\),我们可以求出方程:\(A_1 * x + A_2 * y = gcd(A_1,A_2)\)的解 x,y。此时 x 就是满足当前条件的 \(X\) 序列的第一项的解,\(X_1 = x, X_2 = y\)。我们把 $ gcd(A_1,A_2)$ 当作新的元素,于是得到新的方程:
\(gcd(A_1,A_2) * x + A_3 * X_3 + ... + A_n*X_n + P * Q = B\)。
再继续合并\(gcd(A_1,A_2)\) 和 \(A_3\),求得方程:\(gcd(A_1,A_2) * x + A_3 * y = gcd(gcd(A_1,A_2),A_3)\)的解 x, y。则\(X_3 = y, X_1 = X_1 * x, X_2 = X_2 * x\)。
.......
这样不断递归最后就只剩下\(gcd(A_1,A_2,,,A_n) * x + P * y = B\)
最后再进行一次扩欧即可求出 \(X\) 序列和 \(gcd\)。很明显,当 \(gcd | B\) 时有解。最后答案输出注意取模为正。

AC代码:

// -----------------
//#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
#define rep(i,x,y) for(int i = (x); i <= (y); i ++)

using namespace std;

const int N = 100 + 7;
int A[N],X[N];
int n,p,b;

int exgcd(int a, int b, int &x, int &y) 
{
    if (b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

void solve()
{
    cin >> n >> p >> b;
    rep(i,1,n) cin >> A[i],A[i] %= p;
    // 求gcd(A1,A2,,,An) * x + A(n+1) * y = gcd(A1,A2,,,An,A(n+1))
    X[1] = 1;
    int gcd = A[1];
    for(int i = 2; i <= n; i ++)
    {
        int x,y;
        gcd = exgcd(gcd, A[i], x, y);
        // gcd的系数为 x,则前面所有的系数都得乘一遍 x,注意取模
        for(int j = 1; j < i; j ++) X[j] = X[j] * x % p; 
        X[i] = y;  // 新项的系数为 y
    }
    // 求gcd(A1,A2,,,An) * x + p * y = gcd(A1,A2,,,An,p) ? b
    int x,y;
    gcd = exgcd(gcd, p, x, y);
    for(int i = 1; i <= n; i ++) X[i] = X[i] * x % p;
    if(b % gcd == 0)
    {
        cout << "YES" << endl;
        for(int i = 1; i <= n; i ++)
        {
            X[i] = b * X[i] / gcd % p;
            cout << (X[i] + p) % p << " ";
        }
    }
    else cout << "NO" << endl;
}

signed main()
{
    IOS 
    int T = 1;
    //cin >> T;
    while(T --) { solve(); }
    return 0;
}

标签:一次方程,gcd,多元,序列,include,扩欧,define
From: https://www.cnblogs.com/liqs2526/p/17550327.html

相关文章

  • 数据报告分享|SPSS基于多元回归模型的电影票房预测
    全文链接:https://tecdat.cn/?p=33190原文出处:拓端数据部落公众号本文通过利用回归模型对电影的票房(以及放映场数,观影人数)进行了研究,确定了决定电影的票房的重要因素。并讲述、论证了预测电影的票房是电影投资的至关重要的环节。通过对电影票房预测技术的发展和探讨,深度剖析了电......
  • 多元融合:流媒体传输网络的全盘解法
    我们在寻找「网络」的全盘解法。音视频数字化在消费领域的红利俨然见顶,而产业级视频应用激活了更多场景下的业务模式。与此同时,音视频客户也从单一的业务需求,趋向于多种业务并行存在的需求。固有的网络能满足新兴的业态吗?延时与成本之间存在区间最优解吗?业务的升级切换如何不再......
  • 多元线性回归预测MATLAB代码 代码注释清楚。 可以读取EXCEL数据,使用
    多元线性回归预测MATLAB代码代码注释清楚。可以读取EXCEL数据,使用换自己数据集。很方便,初学者容易上手。ID:8418656625367341......
  • 【HDC.Cloud 2023】新鲜速递:从多元生态、开源到人才培养,让开发者成为决定性力量
    摘要:华为云开发者联盟邀您一起回顾大会精彩时刻。本文分享自华为云社区《【HDC.Cloud2023】新鲜速递:从多元生态、开源到人才培养,让开发者成为决定性力量》,作者:华为云社区精选。华为开发者大会2023(Cloud)7月7日在中国东莞正式揭开帷幕,邀请全球开发者共聚一堂,就AI浪潮之下的产业......
  • R语言使用多元AR-GARCH模型衡量市场风险|附代码数据
    原文链接:http://tecdat.cn/?p=19118最近我们被客户要求撰写关于GARCH的研究报告,包括一些图形和统计输出。本文分析将用于制定管理客户和供应商关系的策略准则假设:贵公司拥有用于生产和分销聚戊二酸的设施,聚戊二酸是一种用于多个行业的化合物。制造和分销过程的投入包括各种......
  • 风变MTP管理课:多元化教学方式引好评
    如今在各种教育方式上,课程都在尽可能地采取更加多元化、新颖的方式,只为让学员能够更快地学到知识。风变MTP管理课在打造的时候,就采用了多元化教学的方式,让学员对课程更感兴趣,更容易理解课堂内容。也正是在多元化的教学方式中,风变MTP管理课帮助学员真正get到了管理技能。风......
  • 多项式模复合的几乎线性算法, 支持多元多项式在线求值的数据结构
    本文简要介绍对于有限域\(\mathbbF_q\),如何快速计算多项式模复合\(f(g(X))\bmodh(X)\),其中\(f,g,h\)均是次数不超过\(n\)的多项式.介绍的思想汇总于2022年Bhargava,Ghosh,Guo,Kumar和Umans的工作:FastMultivariateMultipointEvaluationOverAllFinit......
  • R语言使用多元AR-GARCH模型衡量市场风险|附代码数据
    关于GARCH的研究报告,包括一些图形和统计输出。本文分析将用于制定管理客户和供应商关系的策略准则假设:贵公司拥有用于生产和分销聚戊二酸的设施,聚戊二酸是一种用于多个行业的化合物。制造和分销过程的投入包括各种石油产品和天然气。价格波动可能非常不稳定。营运资金管理一......
  • 浪潮信息张东:多元算力时代,整机软硬协同是发展操作系统的关键
    随着全球数字化转型的加速,数字经济成为经济增长的主引擎,以5G、智算中心为代表的新兴基础设施的不断建设,持续推动着中国服务器及服务器操作系统的发展。经过数十年的探索,中国的服务器操作系统产业新的格局逐渐成型,以龙蜥为代表的三大主流开源Linux社区为根源,大量国内服务器操作系统......
  • 数学 6多元函数积分学
    数二只要求考二重积分的定义、性质、计算和应用。一二重积分的定义和性质1.定义和几何意义积分过程为:在f(x,y)的定义域(是xOy坐标系中的一个平面区域D)中取面积元,则f(x,y)在D上的积分值即为所有的面积元的面积乘以这一点上的函数值的累加和,其积分思路是用无穷多个小圆柱体的体......