欧拉函数欧拉函数（写作\(\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

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))\\&=

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\)可以打包成一个商品，打包尽可能多的商品的情况下让剩余的

首先这个约数公式要记住，具体见这篇题解然后剩下的就是比较简单的套路操作了，最后会化出来\[\sum_{d=1}^{min(n,m)}\sum_{d|x}\sum_{d|y}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rflooru(d)=\sum_{d=1}^{min(n,m)}u(d)(\sum_{d|x}\lfloor\frac{n}{x}\rfloor)(\sum_{d|y}\lf

A.ContestProposal如果\(a_i>b_i\)，则答案加一，令\(\foralli\in[i+1,n],\a_i\leftarrowa_{i-1}\)。submissionB.CoinGames题意：\(n\)枚硬币围成一圈，给出初始硬币状态，每取出一枚正面朝上的硬币并翻转相邻的两枚，没有正面则对方获胜，问先手胜负。令当前正面硬

P3569KAR如何判断某个卡牌顺序能否通过反转形成一个单调不降的序列？使用贪心。我们将第一张卡牌翻到更小的一面。对于后面的卡牌，若小的一面大于等于前一张卡的当前面值，则翻到小的一面。否则若大的一面大于等于前一张卡的当前面值，则翻到大的一面。仍不满足则无解。为了对付单点

欧拉函数\(\varphi(x)\)表示求出\(1\ley\lex,\gcd(x,y)=1\)的\(y\)的数量。对于一个质数\(p\),\(\varphi(p)=p-1\)\(\varphi(p^2)=p^2-\frac{p^2}{p}=p^2-p\)\(\dots\)\(\varphi(p^i)=p^i-p^{i-1}=(p-1)\cdotp^{i-1}\)

本人独自证明，可能存在一定疏漏.题目：\[m!n!(m+n)!\mid(2m)!(2n)!.\]证明：对于每个素数\(p\)，考察式子两边的\(p\)进赋值，即证\[v_p((2m)!(2n)!)\geqv_p(m!n!(m+n)!).\]根据\(p\)进赋值的基本性质与Legendre公式，有\[\begin{align*}v_p((2m)!(2n)!)&=v_p((2m)!)