1.离散对数就是在模\(p\)意义下求出\(\log_ab\)。等价于求出方程\(a^x\equivb\pmodm\)的解。其中的\(x\)就是\(\log_ab\)。当\(a\perpp\)时，BSGS算法可以求解出上面那个方程的解。具体的计算过程如下：我们设块长\(M\)，并且\(x=AM-B\)，那么\(a^{AM}\equiv

P5176公约数\[ans=\sum_{i=1}^{m}\sum_{j=1}^{m}\sum_{k=1}^{p}gcd(ij,jk,ik)\timesgcd(i,j,k)\times(\frac{gcd(i,j)}{gcd(i,k)\timesgcd(j,k))}+\frac{gcd(j,k)}{gcd(i,k)\timesgcd(i,j)}+\frac{gcd(i,k)}{gcd(i,j)\timesgcd(j,k)})\]$\quad$《这东

a:有点神经首先贪心让y尽可能大,x尽可能小，那么我们用两层循环，y从大往小枚举，x从小往大枚举，再大力剪下枝，根据质数的稠密性，这个复杂度是有保证的。不过自己的感觉也大差不差by官方自\(\gcd(L,L+1)=1\)起，总有一个解。我们只需按\((y-x)\)的递减顺序尝试\(L\leqx,y\leq

感觉题目质量比较高，所以挖了个坑（（。X2前三题简单不写洛谷-P10855傻逼赛时想出两种正确思路都他妈的没仔细想，真糖丸了不妨将题目中要求的式子化简。\[\begin{equation}\begin{split}\sum\limits_{i=1}^n\sum\limits_{j=1}^i\gcd(j,i\oplusj)^k&=\sum\limits_{j=1}^n\su

A-ChmaxRush!发现一个数能向哪边覆盖只由再他之后操作且\(v\)比他大的操作决定。所以扫一遍确定方向之后乘起来就好。B-|{floor(A_i/2^k)}|首先不难发现\(<2_{k-1}\)的元素是无用的，因为它们会由\(\ge2^{k-1}\)的元素除以2的幂得到。先想上界。对于\(0\l

数学：最大公约数1.欧几里得算法常识若\(d|x\)且\(d|y\)则\(d|x+y\)且\(d|x-y\)且\(d|ax+by\)\(\gcd(a,0)=a\)辗转相减（更相减损术）\[\gcd(a,b)=\gcd(a,a-b)\]证明思路：证明左右两边的因子完全相同（这是很基本的数学证明方法）intgcd(inta,intb){//注

一、莫比乌斯1、莫比乌斯函数：\(u(n)=\left\{\begin{array}{l}1\qquad\qquadn=1\\0\qquad\qquadn含有平方因子\\(-1)^{k}\qquadn里面所包含质因子数目\end{array}\right.\)令\(\varepsilon(n)=\sum_{d|n}^{n}u(d)=[n=1]\)，那么我们有\(\varepsilon=u\*\1\)

处理区间max，min，gcd，and，or时间复杂度：预处理$O(n)$，查询$O(1)$template<typenameT>classSt{ usingVT=vector<T>; usingVVT=vector<VT>; usingfunc_type=function<T(constT&,constT&)>; VVTST; staticTdefault_func(

欧拉系列欧拉函数欧拉函数\(\varphi(n)\)表示\(1\simn\)内与\(n\)互质的数的个数。性质欧拉函数是积性函数，特别的有\(\varphi(2n)=\varphi(n)\)。\(\sum_{d|n}\varphi(d)=n\)。证明：设\(f(x)\)表示\(\gcd(k,n)=x(k\in[1,n])\)的个数，则\(n=

根据题面，我们将分为多种情况讨论：若a为负数，那么将a,b,c全部取反首先求出data=b^2-4*a*c;1，data<=0cout<<”NO”;否则带入求跟公式：-b/2a+(-)sqrt(data)注意：：gcd(a,b)有可能为负数，此处应用abs(x)取绝对值若开根号data为有理数{-b为2*a的倍数则直接输出b否则输出b/gcd(b,2*a

题意给定集合\(S\)，初始为空，进行\(q\)次修改或查询操作：修改操作将\(x\)加入集合；查询操作给定\(x,s,k\)，要求找到满足\[\max_{u\inS,u+x\les,k|\gcd(u,x)}\{u\oplusx\}\]的最小的\(u\)。sol集合、异或、可查可改，可以自然地想到0/1-Trie。我们假设\(k=1\)，此时不需

GCD的性质总结\(gcd(a_1,a_2,......a_n)=gcd(|a_1|,|a_2|,......|a_n|)\)\(gcd(a,0)=gcd(a,a)=|a|\)\(gcd(a_1,a_2,......a_{n-1},a_n)=gcd(gcd(a_1,a_2),a_3,......a_{n-1},a_n)\)对于不全为零的整数\(a_1,a_2,a_3,......a_{n-1},a_n\),$\forall1<k<n-1\(,

20240806课件marp:truemath:mathjax数论入门整除、同余、数论函数、素数…………………………byRenaMoe不讲证明的地方是因为用处不大而且俺也不会，请自行了解。想要严谨而系统的学习OI相关的数学知识的话，建议读《具体数学》。基础概念oiwiki整除对于正整数

牛客多校8-AHaitangandGameGivenaset\(\textstyleS\),dXqwqandHaitangtaketurnsperformingthefollowingoperations,withdXqwqgoingfirst:Findapair\(\textstyle(x,y)\)suchthat\(\textstylex,y\inS\)and\(\textstyle\gcd(x,y

线性丢番图方程定理设\(a,b\)是整数且\(gcd(a,b)=d\).如果\(d\)不能整除\(c\),那么方程\(ax+by=c\)没有整数解,如果\(d\)可以整除\(c\),则存在无穷个解.另外,如果\((x_0,y_0)\)是方程的一个特解,那么所有解都可以表示为:\[x=x_0+(\frac{b}{d})n,y

08-03题解A根据题目的提示,发现所有数的积是不变的(\(gcd(a,b)*lcm(a,b)=a*b\)),所以差大和大简易证明设\(g=gcd(a,b)\),则\(a=a'g,\)\(b=b'g\),\(lcm(a,b)=a'b'g\)\(gcd(a,b)+lcm(a,b)=g(1+a'b')\)\(a+b=g(a'

B-令人讨厌的字符串问题编辑：evima在大多数情况下，\(f(S,T,X)\)和\(f(S,T,Y)\)的长度相等，这揭示了\(T\)的长度。让我们来看看当已知\(S\)和\(T\)的长度时，在什么条件下\(S\)和\(T\)满足\(f(S,T,X)=f(S,T,Y)\)。例题例如，当\(|S|=6\)和\(|T|=4\)时，让我们考虑当\(S+

思路分析分析样例：见红线，长宽各为2，存在格点；黄线长2宽3，没有格点。考虑延长黄线使得长4宽6，发现有格点。思考格点，如果长和宽都可以被分成\(p\timesl\)的格式，则存在格点。那么，就能想出：推论1：对于\((0\,\0)\)和\((x\,\y)\)之间没有格点，当且仅当\(\gcd(x\,

题目传送容斥思想的一道好题。题目容易转化为：\[2\times\sum_{i=1}^n\sum_{j=1}^n(\gcd(i,j))\-nm.\]直接求和不好求，不妨转换为枚举\(d=\gcd(i,j)\)。那么\(i,j\)应该均为\(d\)的倍数。记\(f(i)=\left\lfloor\frac{n}{i}\right\rfloor\cdot\left\lfloor

题目描述假设：语文课每过  天考试一次；数学课每过 天考试一次；英语课每过  天考试一次。又假设，在昨天，这三门课同时发生了考试。那么从今天开始算起，在接下来的  天时间里，有多少天是没有考试的呢？输入格式第一行：单个整数 第二行：三个整数， 和 。输出格式单个整数：表

幂数！#6222.幂数！（加强版）-Problem-LibreOJ(loj.ac)转写为\(a^2b^3\)要求\(b\)没有平方因子，这样是双射对应。那么即求\[\sum_{i=1}^{\sqrt[3]{n}}\mu^2(i)\left\lfloor\sqrt{\frac{n}{i^3}}\right\rfloor\]后面那个大根号可以整除分块？转化为求\(\mu^2(i)\)的前缀和

（似乎第四场还没补）（没事，问题不大）51002Array-Gift（hdu7482）某种意义上的找规律题？若序列中存在\(a_i=gcd(a_1,a_2,...a_n)\)，则显然\(a_i\)为序列中的最小值，可通过\(n-1\)次取模操作，将其他数变成\(0\)，由于原序列中\(a>0\)，不存在更少的操作次数。若不存在上述\(a_i\)，可通

8.1P6222\[ans=\sum_{T=1}^nT^kS(\frac{n}{k})\sum_{d\midT}d\mu^2(d)\mu(\frac{T}{d})\]令\(f(T)=\sum_{d\midT}d\mu^2(d)\mu(\frac{T}{d})\)，f为积性函数，讨论\(f(p^k)\)的取值。P10636枚举第一个点和第三个点的横纵坐标之差\(i,j\)，第二个点有\(gcd(i,j)-1\)种选择

题目原题链接https://www.luogu.com.cn/problem/P6786题目描述小A有一个长度为n的序列a_1,a_2,...,a_n。他想从这些数中选出一些数b_1,b_2,...,b_k满足：对于所有i(1<=i<=k)，b_i要么是序列b中的最大值，要么存在一个位置j使得b_j>b_i且b_i+b_j+g

动态规划（DP）树形DP数学位运算异或异或前缀和\(s(n)为1到n的数的异或和\)\(s(n)=\begin{cases}1,~~~n\%4==1\\0,~~~n\%4==3\\n,~~~n\%4==0\\n+1,~~~n\%4==2\\\end{cases}\)代码实现如下：autoxorprefix=[&](ll