参考博客exLucas：求\(C_n^m\bmodd\)(\(d\)不一定为质数)1.将\(d\)质因数分解为\(d=p_1^{c_1}\timesp_2^{c_2}\times\cdots\timesp_k^{c_k}\)\(\foralli,j\in[1,k]\),\(p_i^{c_i}\)与\(p_j^{c_j}\)互质，所以可以构造出如下同余方程：\[\begin{cases}a_1\equivC_

欧拉函数欧拉函数（写作\(\varphi(x)\)），表示\(i\in[1,x]且\gcd(i,x)=1\)的\(i\)的数量。乍一看好像很难求，但我们先考虑最简单的情况，即\(x\in\mathbb{P}\)（\(\mathbb{P}\)表示质数集）的情况。首先很容易看出\(\varphi(x)=x-1\)，因为\(x\in\mathbb{P}\)，所以\(\foralli

考虑从高到低位做，不断贪心的一个过程。即假设把当前所有数\(a_i\)看成\(\lfloor\frac{a_i}{2^d}\rfloor\)，有当前最优答案\(ans_d\)；现在把所有数看成\(\lfloor\frac{a_i}{2^{d-1}}\rfloor\)，推出下一步的答案\(ans_{d-1}\)。假设\(/2^d\)时，每一步xor完的序列是\(a_1

题意原题链接求\(1\simn\)的约数个数和sol直接算很困难，考虑换一个角度求\(1\simn\)的约数个数和，等价于求\(1\simn\)分别是范围内几个数的约数对于第\(i\)个值，在\(1\simn\)中，存在\(i,2\cdoti,3\cdoti,\cdots,k\cdoti\)，共\(\lfloor\frac{n}{i}\rfloor\)因此，最终

之前学习的的确是太浅薄了，于是重新学习一下。可以做什么？对于满足条件的积性函数\(f(n)\)，求其前\(n\)项和\(\sum_{i=1}^nf(i)\)。需要准备些什么？设\(N=\{x|x=\lfloor\frac{n}{i}\rfloor\}\)，即为所有整除的不同点值。设\(B=\sqrtn,p_{k}\)代表\(\leB\)的所有质

CF297CSplittingtheUniqueness题解非常好构造题，使我的草稿纸旋转。解法我们记输入的数组为aaa，需要输出的两个数组为b

杜教筛参考来源：OI-Wiki，网上博客线性筛可以在线性时间求积性函数前缀和，而杜教筛可以用低于线性时间求解积性函数前缀和。我们考虑\(S(n)\)就是积性函数的前缀和，所以我们尝试构造关于\(\largeS(n)\)关于\(\largeS(\lfloor\frac{n}{i}\rfloor)\)的递推式。对于任意

数论扩展欧几里得(\(exgcd\))用于求解不定方程\(ax+by=k\)且\(gcd(a,b)|k\)的解。令\(ax+by=gcd(a,b)\)。求\(k\)的话只需要将\(x,y\)乘上\(\dfrac{k}{gcd(a,b)}\)。\[gcd(a,b)=gcd(b,a\%b)\]\[ax_1+by_1=bx_2+(a-\lfloor\dfrac{a}{b}\rfloor\timesb)y_2\]\[ax_1+by

数论分块大部分内容来源于OI-WIKI引理1：\(\\foralla,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\)引理2：\(\lfloor\frac{n}{i}\rfloor\)的取值有\(O(\sqrtn)\

数论分块若可以\(O(1)\)计算\(f(r)-f(l)\)，那么就可以\(O(\sqrtn)\)计算\(\sum^n_{i=1}f(i)(g\lfloor\frac{n}{i}\rfloor)\)。关于\(l,r\)的含义与计算：含义：\(\forallx\in[l,r],\lfloor\frac{n}{x}\rfloor\)相等计算：刚开始\(l\)肯定为\(1\)，如何理解\(r=

A-SubsegmentReverse(abc356A)题目大意给定一个\(1,2,3,...,n\)的排列\(a\)，给定两个数\(l,r\)，左右颠倒\(a[l..r]\)。输出。解题思路按照题意模拟即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::

P6156简单题题解题目大意题目传送门给定\(n,k\)，求\(\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j))\)。\(1\leqn\leq5\times10^6\)题目分析先推导一波式子：\[\begin{aligned}ans&=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j))\\&=

重新整理一下扩欧。扩展欧几里得就是欧几里得算法也就是辗转相除法的扩展应用，扩展后的作用主要为求二元一次方程组的一个解。基本原理众所周知，一个式子是无法确定两个未知数的唯一值的，因此exgcd只能解出一种符合要求的解，但是因为有通解的存在，你可以由这个解推出其他所有的可

T1.P3327知识点：莫比乌斯反演，数论分块我们知道\(d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)==1]\)。所以我们就要求\(\sum^n_{i=1}\sum^m_{j=1}\sum_{x|i}\sum_{y|j}[\gcd(x,y)==1]\)。即为\(\sum^n_{i=1}\sum^m_{j=1}\lfloor\dfrac{n}{i}\rfloor\time

D-Onlyoneoftwohttps://atcoder.jp/contests/abc341/tasks/abc341_d数论，二分求第K大设\(L\)是\(N\)和\(M\)的最小公倍数。那么，有\(\lfloor\frac{X}{L}\rfloor\)个不大于\(X\)的正整数能被\(\lfloor\frac{X}{L}\rfloor\)整除，因此有\(\lfloor\frac{X}{N

【NOI2010】能量采集题解谨纪念我的第一道手推出来的莫反题。题目大意：已知\(n\)，\(m\)，求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)\)。首先变形一手：\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)=2\sum\limits_{i=1}^n\sum\limits_{j=

狄利克雷卷积与莫比乌斯反演主要内容数论函数狄利克雷卷积积性函数莫比乌斯反演数论分块提要\(a\botb\)表示\(a\)与\(b\)互质。数论函数数论函数是一类定义域是正整数的函数，可以类比数列。加法，数乘比较简单，略过。狄利克雷卷积定义两个数论函数的狄利克雷卷

有点菜，现在才会。之前好多篇都烂尾了，这篇不能了。数论分块往往适合于带有向下取整的题目，即求\(\sumf(i)g(\lfloor\frac{n}{i}\rfloor)\)的值。当经过某些处理后可以\(O(1)\)求出\(f(r)-f(l)\)的值时，数论分块可以\(O(\sqrt{n})\)求出上述式子的值。向下取整\(\lfloor

2024040前言离散数学是本书的重点，而整数又是离散数学的中心议题。数论是讨论整数性质的重要数学分支，因此我们要来探索它。​ ——《具体数学》第四章标有*的为拓展内容，或者说比较难的题目，但它们都非常有趣。部分题目的代

P1829[国家集训队]Crash的数字表格/JZPTAB不妨假设\(n<m\)。\[\begin{aligned}\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\gcd(i,j)}&=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\dfrac{ij}{d}\\\\&=\sum_{d=1}^n\sum_{i

题目链接：CF或者洛谷给个莫反题解，讲讲常规套路题目要求满足没有\(a_k\mida_i与a_k\mida_j\)的\((i,j)\)的对数，显然即不存在\(a_k\mid\gcd(a_i,a_j)\)。稍微拓展下，如果不存在整除多个数，那么显然不整除它们的\(\gcd\)即可，因为它们的公因数即为满足的最大数，如果为

欧拉函数欧拉函数（写作\(\varphi(x)\)），表示\(i\in[1,x]且\gcd(i,x)=1\)的\(i\)的数量。乍一看好像很难求，但我们先考虑最简单的情况，即\(x\in\mathbb{P}\)（\(\mathbb{P}\)表示质数集）的情况。首先很容易看出\(\varphi(x)=x-1\)，因为\(x\in\mathbb{P}\)，所以\(\foralli

题目大意：\(f(x)=\begin{cases}x,1\lex\le9\\f(x的各数位之和),x>9\\\end{cases}\)求\(\sum_{i=1}^{n}f(i)\)。根据打表找规律，我们会发现\(f(x)=(x-1)\bmod9+1\)。所以\(\sum_{i=1}^{n}f(i)\)\(=\sum_{i=1}^{\lfloor\frac{n}{9}\rfloor\cdot9}f(x)+\sum_{i=\l

蓝书上的错误原因在不一定有\(x_1-\lfloorpx_1\rfloor+q=\lfloorx_1-px_1\rfloor+q\)，因为减号不一定能够移进移出，但是加号可以我们现在要证明的就是\(x_1-\lfloorpx_1\rfloor≥x_2-\lfloorp(x_2+q)\rfloor\)，既然减号不可以我们就移项利用加法也就是证\(x_1+\lfloorp(x_2+q)

link：https://codeforces.com/gym/105143Groupcontests：https://codeforces.com/group/DWEH34LQgT/contest/521901题意：有\(n\)件\(A\)物品，\(m\)件\(B\)物品，两种物品价值分别是\(a,b\)，若干件\(A\)和若干件\(B\)可以打包成一个商品，打包尽可能多的商品的情况下让剩余的