首页 > 其他分享 >(数论)裴蜀定理

(数论)裴蜀定理

时间:2024-02-29 20:33:54浏览次数:27  
标签:gcd 数论 res 定理 int ax 裴蜀

裴蜀定理内容:


  ${ax+by=c,x\in Z^*,y\in Z^*}$成立的充要条件是${\gcd(a,b)|c}$。$Z^*$表示正整数集。

 

设${s=\gcd(a,b)}$,显然${s|a}$,并且${s|b}$

又因为${x,y\in Z^*}$

所以${s|ax,s|by}$
显然要使得之前的式子成立,则必须满足$c$是$a$和$b$的公约数的倍数
又因为$x$和$y$是正整数

所以$c$必然是$a,b$最大公约数的倍数。

裴蜀定理推广: 若两个素数互素,那么设分别为 $x y$ 那么有 $ax+by=N$,$N$为任何数,也就是若两个数互素,那么他们可以组合成任何数

 

//【模板】裴蜀定理
//https://www.luogu.com.cn/problem/P4549
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,res=1; cin>>n;
    vector<int>a(n+1); cin>>a[1];
    for(int i=2;i<=n;i++) cin>>a[i],res=__gcd(a[i],res);
    cout<<res<<endl;
    return 0;
}

 

标签:gcd,数论,res,定理,int,ax,裴蜀
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18045385

相关文章

  • 杜教筛——亚线性处理数论函数求和
    问题引入给定一个数论函数\(f(x)\),求\(\sum\limits_{i=1}^nf(i)\)。对\(n\le10^7\)甚至\(n\le10^8\)都是好做的,\(\mathcalO(n)\)解决即可,但如果\(n<2^{31}\)呢?这就需要亚线性时间复杂度的算法,杜教筛就是其一。杜教筛杜教筛是一种能在幂时间\(\mathcalO(......
  • 花神的数论题(数位dp)
    花神的数论题题目描述设\(\text{sum}(i)\)表示\(i\)的二进制表示中\(1\)的个数。给出一个正整数\(N\),花神要问你\(\prod_{i=1}^{N}\text{sum}(i)\),也就是\(\text{sum}(1)\sim\text{sum}(N)\)的乘积。数据范围\(1\leN\le10^{15}\)。解法首先我们要......
  • 矩阵树定理
    记结论如果有一条\((i,j)\)的边无向图生成树计数设\(D\)为度数矩阵,\(A\)为邻接矩阵。那么令\(L=D-A\)。则生成树为\(L\)去掉任意一行一列的\(Det(L)\)。mat[i][i]++,mat[j][j]++,mat[i][j]--,mat[j][i]--有向图外向树计数设\(D\)为入度矩阵,\(A\)为邻接矩......
  • 基础数论学习笔记
    1.辗转相减利用辗转相减法求最大公约数,即\(gcd(a,b)\)。假设\(a>b\),则gcd(a,b)=gcd(a−b,b),不断的利用大的数减去小的数,就能得到最大公约数。1.证:若\(n,m(n>m)\)互质,则$(n-m),m$互质若不互质,则设\(n-m=k*a,m=k*b\)\(\thereforen-k*b=k*a......
  • 鞅与停时定理
    好高妙!大致思想是给每个局面构造一个势能函数\(F(a_1,a_2,\ldots,a_n)\),使得\(\sumE(F(a'_1,a'_2,\ldots,a'_n))-E(F(a_1,a_2,\ldots,n))=-1\),其中\(a'\)取遍\(a\)的后继状态。这样我们就能直接用终态的势能函数减去初始态的势能函数计算期望,即答案为\(E(S)......
  • Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341)D - Only one of two
    目录链接题面题意题解代码总结链接D-Onlyoneoftwo题面题意求第\(k\)个只能被\(N\)或\(M\)整除的数题解\([1,x]\)中的能被\(n\)整除的数有\(\lfloor\frac{x}{n}\rfloor\)个\([1,x]\)中的能被\(m\)整除的数有\(\lfloor\frac{x}{m}\rfloor\)个\([1,x]\)中的能被\(n\)......
  • 【计算机网络】物理层重要公式:奈氏准则&香农定理
    奈氏准则&香农定理失真影响失真程度的因素:1.码元传输速率2.信号传输距离3.噪声干扰4.传输媒体质量码间串扰码间串扰指接收端收到的信号波形失去了码元之间清晰界限的现象。信道带宽:最高频-最低频。超过的部分发生码间串扰,小于的部分发生失真?奈氏准则奈氏准则在理想......
  • 数论函数
    数论函数常见数论函数\(\epsilon(n)=[n=1]\)\(I(n)=1...\)\(id(n)=n\)\(id^k(n)=n^k\)\(\mu\)莫比乌斯函数\(\phi\)欧拉函数\(\tau\)约数个数\(\sigma\)约数和欧拉函数\(\phi(n)\)表示的是小于等于n和n互质的数的个数,是积性函数\(\phi(p^k)=p^k-p^{k-1}\)\(n=\sum_......
  • 数学笔记(1)-勾股定理与勾股数
    勾股定理,是一个基本的几何定理,指直角三角形的两条直角边的平方和等于斜边的平方。中国古代称直角三角形为勾股形,并且直角边中较小者为勾,另一长直角边为股,斜边为弦,所以称这个定理为勾股定理,也有人称商高定理。勾股定理现约有500种证明方法,是数学定理中证明方法最多的定理之一。勾......
  • 数论分块性质优化DP状态
    6311.mobitel给定一个r行s列的矩阵,每个格子里都有一个正整数。问如果从左上角走到右下角,且每次只能向右或向下走到相邻格子,那么使得路径上所有数的乘积不小于n的路径有多少条?对于100%的数据,1<=r,s<=300,1<=n<=10^6,矩阵中的数不超过10^6。so,一个普通的思想就是设f[......