zcmimi's blog

arrow_back数论共123篇文章

avatar
zc
2020-03-20 16:33:00
查看原题

点击跳转

\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{\gcd(i,j)} \\ =\prod_{i=1}^n\prod_{j=1}^n\frac{ij}{\gcd(i,j)^2} \\ =\prod_{i=1}^n\prod_{j=1}^n ij \prod_{d=1}^n {\frac 1{d^2}}^{\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]} \\ =(n!)^{2n} \left (\prod_{d=1}^n d^{\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]} \right )^{-2}

其中:

\prod_{d=1}^n d^{\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]} \\ =\prod_{d=1}^n d^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor} [\gcd(i,j)=1]} \\ =\prod_{d=1}^n d^{-1+2\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \varphi(i)}

因为mod=104857601是质数,使用可以用欧拉定理

avatar
zc
2020-03-20 12:57:00
查看原题

点击跳转

带 套 路 题

\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j) \\ =\sum_{d=1}^n \mu^2(d) d \sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d] \\ =\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k[\gcd(i,j)=1]

S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k

=\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor}\mu^2(d) d^{k+1} \mu(x) x^k S(\left \lfloor \frac n{dx} \right \rfloor)

T=dx

=\sum_{T=1}^n \sum_{d|T} \mu^2(d) d^{k+1} \mu(\frac Td) (\frac Td)^k S(\left \lfloor \frac nT \right \rfloor) \\ =\sum_{T=1}^n S(\left \lfloor \frac nT \right \rfloor) T^k \sum_{d|T} d \mu^2(d)\mu(\frac Td)

如何快速求令S(n)?

设:

F(n)=\sum_{i=1}^n i^k

G(n)=\sum_{i=1}^n F(i)

那么

S(n)=\sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^nF(i) \\ =G(2n)-2G(n)

筛出F的前缀和,然后筛S(n)

优化:

因为模数是质数,根据欧拉定理: 对于互质的a,n满足a^{\varphi(n)} \equiv 1\pmod n

可以k=k \mod 998244352

求后半部分

f(n)=\sum_{d|n} d \mu^2(d)\mu(\frac nd)

如何线性求f(n)?

f(n)是若干个积性函数的卷积,所以f(n)也是积性函数

那么f(n)=f(p^k)f(\frac n{p^k})

f(1)=1

f(p^1)=p-1(带入即可得到)

f(p^2)=-p(带入即可得到)

f(p^k)=0(k\ge 3)

d\frac nd中必然有一个有平方因子,所以\mu(d)\mu(\frac nd)必有一项为0

所以f(p^k)=0(k\ge 3)

接下来就可以线性筛f(n)

avatar
zc
2020-03-19 23:44:00
查看原题

点击跳转

经过一番化简后变成了:

\sum_{i=1}^{\sqrt{2n}} \sum_{x=L}^{R} [\gcd(i,x)=1] \\ L=Max(1,i-\lfloor {n\over i}\rfloor) \\ R=Min(i-1,\lfloor {n\over i }\rfloor)

莫比乌斯反演

\sum_{i=1}^{\sqrt{2n}} \sum_{j=l}^{R} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\sqrt{2n}} \sum_{j=l}^{R} \sum_{k|i,k|j} \mu(k) \\ =\sum_{i=1}^{\sqrt{2n}}\sum_{k|j,k\in[L,R]} \mu(k)

avatar
zc
2020-03-19 20:28:00
查看原题

点击跳转

\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} \sum_{x|i,x|j}\mu(x) \\ =\sum_{x=1}^n\mu(x) \left \lfloor \frac A{dx} \right \rfloor \left \lfloor \frac B{dx}\right \rfloor

avatar
zc
2020-03-19 19:22:00
查看原题

点击跳转

x分解质因数结果为x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}

f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)

f(x)其实就是d(x),x的约数个数

p_1^{k_1}的约数有1,p_1,p_1^2,\cdots,p_1^{k_1}

p_2^{k_2}的约数有1,p_2,p_2^2,\cdots,p_2^{k_2}

\cdots

p_n^{k_n}的约数有1,p_n,p_n^2,\cdots,p_n^{k_n}

根据乘法原理,d(x)=(k_1+1)(k_2+1)\cdots (k_n+1)

首先可以想到的是

\sum_{i=l}^r f(i)=\sum_{i=1}^r f(i) - \sum_{i=1}^{l-1} f(i)

那么

\sum_{i=1}^n f(i) \\ =\sum_{i=1}^n \sum_{j|i}1

换个枚举顺序

=\sum_{j=1}^n \sum_{j|i}1 \\ =\sum_{j=1}^n \left \lfloor \frac nj\right \rfloor

最后数论分块就可以了

avatar
zc
2020-03-19 17:10:00
查看原题

点击跳转

首先L=\left \lceil \frac LK\right \rceil,H=\left \lceil \frac HK\right \rceil

问题转化为在[L,H]中取 N\gcd=1的数 的方案数

f_i为选出 N个不完全相同\gcd=i的数 的方案数

x[L,R]i的倍数的个数,x=\sum_{j=L}^H [i|j]=\left \lfloor \frac Hi \right \rfloor-\left \lfloor \frac Li \right \rfloor

暂时令f_i=x^N-x(所有减去完全相同的)

这时候f_i实际上是选出 N个不完全相同i|\gcd的数 的方案数

假设我们已经知道了f_{2i},f_{3i},...的最终结果

那么把f_i减去f_{2i},f_{3i},...就可以了

avatar
zc
2020-03-19 15:44:00
查看原题

点击跳转

\sum_{i=1}^n\sum_{j=1}^n lcm(A_i,A_j)

a_i = \sum_{j=1}^n [A_j=i]

那么

ans = \sum_i^n \sum_j^n a_ia_j \frac{ij}{\gcd(i,j)} \\ = \sum_{d=1}^n \frac 1d \sum_{i=1}^n \sum_{j=1}^n a_ia_j ij[\gcd(i,j)=d] \\ = \sum_{d=1}^n \sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd}d \times a_{id}a_{jd}ij[\gcd(i,j)=1] \\ \text{唉,到这里我就不会了} \\ =\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}a_{ip}a_{jp}ij\sum_{d|i,d|j}\mu(d) \\ =\sum_{p=1}^np\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{n/dp}\sum_{j=1}^{n/dp}a_{idp}a_{jdp}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\sum_{i=1}^{n/q}\sum_{j=1}^{n/q}a_{iq}a_{jq}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\left(\sum_{i=1}^{n/q}a_{iq}i\right)^2

avatar
zc
2020-03-18 02:07:00
查看原题

点击跳转

前置知识:

  1. 杜教筛(包括狄利克雷卷积)

  2. 数论分块

  3. 欧拉函数 或 莫比乌斯函数

(会杜教筛的大佬上述都会吧)

欧拉函数卷积推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)

根据 \sum\limits_{i|n}\varphi(n)=n (1 * \varphi = Id)

= \sum_{i=1}^n\sum_{j=1}^n ij \sum_{k|i,k|j} \varphi(k)

调换枚举顺序

= \sum_{k=1}^n \varphi(k) \sum_{k|i,k|j} ij \\ = \sum_{k=1}^n \varphi(k) \sum_{k|i}i \sum_{k|j}j \\ = \sum_{k=1}^n \varphi(k) (\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}ki)^2 \\ = \sum_{k=1}^n \varphi(k) k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2

莫比乌斯函数推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j) \\ =\sum_{d=1}^n d \sum_{i=1}^n\sum_{j=1}^n ij [gcd(i,j)=d] \\ =\sum_{d=1}^n d^3 \sum_{i=1}^{\left \lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left \lfloor\frac nd\right\rfloor} ij [gcd(i,j)=1] \\ =\sum_{d=1}^n d^3 \sum_{i=1}^{\left \lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left \lfloor\frac nd\right\rfloor} ij \sum_{k|i,k|j}\mu(k) \\ =\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k) \sum_{k|i,k|j} ij \\ =\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k) k^2(\sum_{k|i}i)^2

为了方便,设sum(T)=\sum_{i=1}^T i

=\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k)k^2sum(\left \lfloor \frac n{dk}\right \rfloor)^2

T=dk

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 \sum_{d|T}d^3 \frac{T^2}{d^2}\mu(\frac Td) \\ =\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2\sum_{d|T}d\mu(\frac Td)

其中: \sum_{d|T}d\mu(\frac Td)=\varphi(T)(\mu * Id = \varphi)

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2 \varphi(T)

上述两种方法推导出的最终结果是一样的

接下来:

\sum_{k=1}^n \varphi(k)用杜教筛求出前缀和

k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2可以用数论分块求解

avatar
zc
2020-03-17 23:04:00
查看原题

点击跳转

一个点(x,y)和原点之间的点数为gcd(x,y)-1

n<m

设t=\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) \\ =\sum_{d=1}^n d \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d] \\ =\sum_{d=1}^n d \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor} [gcd(i,j)=1] \\ =\sum_{d=1}^n d \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor} \sum_{k|gcd(i,j)}\mu(k) \\ =\sum_{d=1}^n d \sum_{k=1}^{\left \lfloor \frac nd \right \rfloor}\mu(k)\left \lfloor \frac n{dk} \right \rfloor \left \lfloor \frac m{dk} \right \rfloor \\ ans = 2*t-n*m

记得long long

avatar
zc
2020-03-17 17:16:00
查看原题

点击跳转

7/13
Search
search