- 2024-08-18Some 困难的数论
1.离散对数就是在模\(p\)意义下求出\(\log_ab\)。等价于求出方程\(a^x\equivb\pmodm\)的解。其中的\(x\)就是\(\log_ab\)。当\(a\perpp\)时,BSGS算法可以求解出上面那个方程的解。具体的计算过程如下:我们设块长\(M\),并且\(x=AM-B\),那么\(a^{AM}\equiv
- 2024-08-18P5176 公约数
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$《这东
- 2024-08-16arc137
a:有点神经首先贪心让y尽可能大,x尽可能小,那么我们用两层循环,y从大往小枚举,x从小往大枚举,再大力剪下枝,根据质数的稠密性,这个复杂度是有保证的。不过自己的感觉也大差不差by官方自\(\gcd(L,L+1)=1\)起,总有一个解。我们只需按\((y-x)\)的递减顺序尝试\(L\leqx,y\leq
- 2024-08-14MX Weekly 赛时/VP 记录
感觉题目质量比较高,所以挖了个坑((。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
- 2024-08-13ARC182 题解
A-ChmaxRush!发现一个数能向哪边覆盖只由再他之后操作且\(v\)比他大的操作决定。所以扫一遍确定方向之后乘起来就好。B-|{floor(A_i/2^k)}|首先不难发现\(<2_{k-1}\)的元素是无用的,因为它们会由\(\ge2^{k-1}\)的元素除以2的幂得到。先想上界。对于\(0\l
- 2024-08-12约束及其有关问题
数学:最大公约数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){//注
- 2024-08-12积性函数(莫比乌斯)
一、莫比乌斯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\)
- 2024-08-12关于gcd
处理区间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(
- 2024-08-12欧拉系列
欧拉系列欧拉函数欧拉函数\(\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=
- 2024-08-10P9750 [CSP-J 2023] 一元二次方程题目总结
根据题面,我们将分为多种情况讨论:若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
- 2024-08-09[lnsyoj2246/luoguCF979D]Kuro and GCD and XOR and SUM
题意给定集合\(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\),此时不需
- 2024-08-08GCD (最大公因数)的性质
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\(,
- 2024-08-08数学
20240806课件marp:truemath:mathjax数论入门整除、同余、数论函数、素数…………………………byRenaMoe不讲证明的地方是因为用处不大而且俺也不会,请自行了解。想要严谨而系统的学习OI相关的数学知识的话,建议读《具体数学》。基础概念oiwiki整除对于正整数
- 2024-08-08牛客多校 A 题题解
牛客多校8-AHaitangandGameGivenaset\(\textstyleS\),dXqwqandHaitangtaketurnsperformingthefollowingoperations,withdXqwqgoingfirst:Findapair\(\textstyle(x,y)\)suchthat\(\textstylex,y\inS\)and\(\textstyle\gcd(x,y
- 2024-08-06线性丢番图方程
线性丢番图方程定理设\(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
- 2024-08-0608-04 题解
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'
- 2024-08-05ARC181 - B - Annoying String Problem
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+
- 2024-08-05洛谷-P9830 题解
思路分析分析样例:见红线,长宽各为2,存在格点;黄线长2宽3,没有格点。考虑延长黄线使得长4宽6,发现有格点。思考格点,如果长和宽都可以被分成\(p\timesl\)的格式,则存在格点。那么,就能想出:推论1:对于\((0\,\0)\)和\((x\,\y)\)之间没有格点,当且仅当\(\gcd(x\,
- 2024-08-05P1447 [NOI2010] 能量采集
题目传送容斥思想的一道好题。题目容易转化为:\[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
- 2024-08-05没有考试的天数(YACS)
题目描述假设:语文课每过 天考试一次;数学课每过 天考试一次;英语课每过 天考试一次。又假设,在昨天,这三门课同时发生了考试。那么从今天开始算起,在接下来的 天时间里,有多少天是没有考试的呢?输入格式第一行:单个整数 第二行:三个整数, 和 。输出格式单个整数:表
- 2024-08-04【笔记】数论 2024.8.4
幂数!#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)\)的前缀和
- 2024-08-042024杭电多校第5场
(似乎第四场还没补)(没事,问题不大)51002Array-Gift(hdu7482)某种意义上的找规律题?若序列中存在\(a_i=gcd(a_1,a_2,...a_n)\),则显然\(a_i\)为序列中的最小值,可通过\(n-1\)次取模操作,将其他数变成\(0\),由于原序列中\(a>0\),不存在更少的操作次数。若不存在上述\(a_i\),可通
- 2024-08-032024.8 做题记录
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\)种选择
- 2024-08-03洛谷P6786
题目原题链接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
- 2024-08-02ACM notes
动态规划(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