zcmimi's blog

arrow_back数论共123篇文章

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

点击跳转

f=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \\ f=\sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} [gcd(i,j)=1] \\ \because \sum_{x|n} \mu(x) = [n=1] \\ \therefore f= \sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} \sum_{k|gcd(i,j)} \mu(k) \\ f=\sum_{k=1}^{\left \lfloor \frac ad \right \rfloor}\mu(k)\left \lfloor \frac a{dk} \right \rfloor \left \lfloor \frac b{dk} \right \rfloor

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

点击跳转

把题目强行转换为[POI2007]ZAP-Queries

Ans((1,b),(1,d))-Ans((1,b),(1,c-1))-Ans((1,a-1),(1,d))+Ans((1,a-1),(1,c-1))

f=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \\ f=\sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} [gcd(i,j)=1] \\ \because \sum_{x|n} \mu(x) = [n=1] \\ \therefore f= \sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} \sum_{k|gcd(i,j)} \mu(k) \\ f=\sum_{k=1}^{\left \lfloor \frac ad \right \rfloor}\mu(k)\left \lfloor \frac a{dk} \right \rfloor \left \lfloor \frac b{dk} \right \rfloor

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

点击跳转

n<m \prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)=d]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor}[\gcd(i,j)=1]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \mu(i) \left \lfloor \frac n{id}\right \rfloor \left \lfloor \frac m{id}\right \rfloor}

数论分块套数论分块会tle,继续老套路优化

T=id

=\prod_{T=1}^n\sum_{d|T}{f_d}^{\mu(\frac Td) \left \lfloor \frac n{T}\right \rfloor \left \lfloor \frac m{T}\right \rfloor}

可以先预处理出函数s(T)=\sum_{d|T}{f_d}^{\mu(\frac Td)}的前缀积

然后就可以做到数论分块O(\sqrt n)的复杂度了

avatar
zc
2020-03-14 20:35:00
查看原题

点击跳转

n<m,\sigma(d)d的约数和

先不考虑\sigma(\gcd(i,j))\le a

\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j)) \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d] \\ =\sum_{d=1}^n \sigma(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 \sigma(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sigma(d) \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor} \mu(x) {\left \lfloor \frac n{dx} \right \rfloor}{\left \lfloor \frac m{dx} \right \rfloor}

T=dx

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

考虑a的限制

g(T)=\sum_{d|T}\sigma(d) \mu(\left \lfloor \frac Td \right \rfloor)

可以发现当d\ge a的时候才会产生贡献

将询问按a排序

每次询问的时候,按倍数枚举找到所有新的可以产生贡献的T,

动态修改g(T),可以选择树状数组这种又短常数又小的好东西

avatar
zc
2020-03-14 03:42:00
查看原题

点击跳转

求: \sum_{i=1}^n\sum_{j=1}^mlcm(i,j)

n<m \sum_{i=1}^n\sum_{j=1}^mlcm(i,j) \\ =\sum_{i=1}^n\sum_{j=1}^m \frac{ij}{\gcd(i,j)} \\ =\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \frac {ij}d[\gcd(i,j)=d]

i'=\left \lfloor \frac id \right \rfloor,j'=\left \lfloor \frac jd \right \rfloor

\\ =\sum_{d=1}^n\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} ijd[\gcd(i,j)=1]

\sum\limits_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum\limits_{j=1}^{\left \lfloor \frac md \right \rfloor} ij[\gcd(i,j)=1]拆出来,

sum(n,m)=

\sum_{i=1}^n\sum_{j=1}^n ij[\gcd(i,j)=1] \\ =\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)} ij\mu(d) \\ =\sum_{d=1}^n\sum_{d|i}\sum_{d|j} ij\mu(d)

i'=\left \lfloor \frac id \right \rfloor,j'=\left \lfloor \frac jd \right \rfloor

=\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\left \lfloor \frac nd\right \rfloor}\sum_{j=1}^{\left \lfloor \frac md\right \rfloor} ij

g(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^mij

g(n,m)=\frac{n(n+1)}2\cdot \frac{m(n+1)}2

最后

ans=\sum_{d=1}^n d\cdot sum(\left\lfloor \frac nd \right\rfloor,\left\lfloor \frac md \right\rfloor) \\ sum(n,m)=\sum_{d=1}^n\mu(d)d^2 g(\left\lfloor \frac nd \right\rfloor,\left\lfloor \frac md \right\rfloor)

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

点击跳转

可以先转化为前缀和再相减

问题变为了求:

\sum_{i=1}^n \sum_{j|i}j

考虑每个约数d,它的贡献次数为\left \lfloor \frac nd\right \rfloor

那么答案就是

\sum_{d=1}^n d\left \lfloor \frac nd\right \rfloor

直接数论分块即可

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

点击跳转

\sum_{i=1}^n\sum_{j=1}^m[i≠j](n \bmod i)(m \bmod j),n,m\le 10^9

数论分块

先不考虑i!=j

\sum_{i=1}^n\sum_{j=1}^m(n \bmod i)(m \bmod j) \\ =\sum_{i=1}^n(n-i\left \lfloor \frac ni\right \rfloor)\sum_{j=1}^m(m-j\left \lfloor \frac mj\right \rfloor)

考虑i=j,设k=\min(n,m)

\sum_{i=1}^n\sum_{j=1}^m(n \bmod i)(m \bmod j)[i=j] \\ =\sum_{i=1}^k(n \bmod i)(m \bmod i) \\ =\sum_{i=1}^k(n-i\left \lfloor \frac ni \right \rfloor)(m-i\left \lfloor \frac mi \right \rfloor) \\ =\sum_{i=1}^knm-ni\left \lfloor \frac mi \right \rfloor-mi\left \lfloor \frac ni \right \rfloor+i^2 \left \lfloor \frac{nm}{i^2}\right \rfloor \\ =knm-n\sum_{i=1}^k i\left \lfloor \frac mi \right \rfloor-m\sum_{i=1}^ki\left \lfloor \frac ni \right \rfloor+\sum_{i=1}^ki^2\left \lfloor \frac ni \right \rfloor\left \lfloor \frac mi \right \rfloor

两个相减就是答案

提示: \sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}6

推导过程:

S=\sum_{i=1}^n{i^2}

(n+1)^3-n^3=3n^2+3n+1

n^3-(n-1)^3=3(n-1)^2+3(n-1)+1

\cdots

2^3-1^3=3\times1^2+3\times 1+1

上面n个式子相加得到:

(n+1)^3-1=3(1^2+2^2+\dots+n^2)+3(1+2+\dots+n)+n

\therefore S=\frac13\left[ (n+1)^3-1- \frac12n(n+1) \right]=\frac{n(n+1)(2n+1)}6

avatar
zc
2020-03-11 20:34:00
查看原题

点击跳转

\sum_{i=0}^k {n \choose i} \bmod 2333

p=2333 \sum_{i=0}^k {n \choose i} \bmod p \\ =\sum_{i=0}^k {\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac ip \right \rfloor} {n \bmod p \choose i\bmod p}\bmod p \\ ={\left \lfloor \frac np \right \rfloor \choose 0}\sum_{i=0}^{p-1}{n \bmod p \choose i}+{\left \lfloor \frac np \right \rfloor \choose 1}\sum_{i=0}^{p-1}{n \bmod p \choose i}+ \cdots+ {\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac kp \right \rfloor}\sum_{i=0}^{k \bmod p}{n \bmod p \choose i}

f(n,k)=\sum_{i=0}^k {n \choose i}

原式可以转化为:

f(n \bmod p,p-1) \cdot f(\left \lfloor \frac np \right \rfloor,\left \lfloor \frac kp \right \rfloor -1)+{\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac kp \right \rfloor} f(n\bmod p,k\bmod p)

avatar
zc
2020-03-11 13:59:00
查看原题

点击跳转

bsgs裸题

avatar
zc
2020-03-11 00:41:00
查看原题

点击跳转

给出n,m{n+m} \choose m

8/13
Search
search