点个赞吧，球球了~下一篇:$浅谈同余2(扩展欧几里得，中国剩余定理，BSGS)$https://www.acwing.com/file_system/file/content/whole/index/content/7882318/ $\LaTeX$太多了，分成几个部分0x00总写(瞎说)同余是数学中非常重要的东西，这里会写出同余的基本运用若$a\bmodm=b\bmo......

//createdon23.04.30目录在线O(1)逆元在线O(1)逆元给定质数模数\(p\)，多次查询一个数\(a\)的逆元，强制在线。我们有一个\(O(p^{\frac{2}{3}})\)的预处理，\(O(1)\)查询的做法。Farey序列即\(F_n\)表示所有分母不超过\(n\)的最简真分数构成的有序数列（左右端......

初等数论素数定义设整数\(p\ne0,\pm1\)。如果\(p\)除了平凡约数以外没有其他约数，那么称\(p\)为素数（不可约数）。若整数\(a\ne0,\pm1\)且\(a\)不是素数，则称\(a\)为合数。——————OIWiki素数的判定（素性测试）如何判断一个数\(x\)是不是质数？很显然我们可......

最近看到这个题，想到了一种比较简单的做法。首先，我们考虑给\(x\)乘以一非零整数\(u\)，如果我们能求出\(\frac{1}{xu}\)，我们就可以通过再乘以\(u\)得到答案。考虑让\(u\)和\(xu\bmodp\)比较接近\(0\)，预处理\(|k|\)比较小的所有\(\frac{1}{k}\)。考虑分块：设\(x=......

ProblemDescriptionApex实验室里培养了很多种类的细菌。细菌的繁殖遵循如下规则：第k种细菌在第t个单位时间内新增的数量为k^t。例如，k=2,t=4时,第种细菌的总数为2+4+8+16。现在，实验室里一共有n种细菌，分别为1,2,3,…,n。在第1单位时间结束后，第k种细菌的个数为k个。求第m个单位时......

扩展欧几里得算法基本知识整除的基本定义与性质定义\(设a,b∈Z且a≠0，若b除以a余数为0，则称a整除b，记为a∣b。若a不能整除b，则称a\nmidb。\)性质1\(a∣b⟺−a∣b⟺a∣−b⟺|a|∣|b|。\)性质2\(a∣b且b∣c⇒a∣c。\)性质3\(c∣a且c∣b⇒c∣na+mb......

问题给定\(a\)和\(b\)，保证\(a\)与\(b\)互质，求\(ax\equiv1\pmod{b}\)求解方式1扩展欧几里得能求\(ax+by=\gcd(a,b)\)，因为a与b互质，等价于求\(ax+by=1\),即\(ax=1-by\)，就等同于求\(ax\equiv1\pmod{b}\)求解方式2根据费马小定理易知当\(b\)为质数时，在\(a^{b-1}\equiv1\pmod{b}\)，......

一、逆元定义二、求逆元的方法1.扩展欧几里得(exgcd)适用于单个查找或者模p很大的情况下,p不是质数的时候也可以使用此处是线性同余方程(a*x≡b(modm))的特殊情况(b=1)所求解x=x*b/d%m，若要保证x是最小的正整数则x=(x%m+m)%m1#include<iostream>2usingnamespace......

1.基本公式相当于直接去求\(​\frac{1}{n!}\)也就是说咱们要是去求\(\frac{1}{n}\)逆元2.怎么求逆元？代码模板LLexgcd(LLa,LLb,LL&x,LL&y)//扩展欧几里得算法{ if(b==0) { x=1,y=0; returna; } LLret=exgcd(b,a%b,y,x); y-=a/b*x; returnret;}LLg......

扩展欧几里得三种做法1.求解ax+by=gcd(a,b)ax+by=b*x1+a%b*y1==>x=y1;y=x1-a/b*y1;若b=0时，x=1,y=0;2.求解ax+by=c求解出a*x0+b*y0=d(若d|c则优解，不可整除则无解)然后x=x0*c/d,y=y0*c/d只是一个特解，不一定是最优解,可以求解齐次方程的通解，然后可以3.求解a*x......