zcmimi's blog

arrow_back数论分块共10篇文章

avatar
zcmimi
2020-06-09 16:22:00

DZY Loves Math

题意:

对于正整数n,定义f(n)n所含质因子的最大幂指数

例如f(1960)=f(2^3\cdot 5^1\cdot 7^2)=3,f(10007)=1,f(1)=0

给定正整数a,b,求$\sum\limits_{i=1}^a\s

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 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-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 23:16:00
查看原题

点击跳转

题意:求第k个没有完全平方数因子的数

可以发现答案具有单调性,可以二分答案,然后判断[1,n]中满足条件的个数是否为k

这个结果为

1(0个平方因子)的倍数-【4,9,16,25,...】(1个平方因子)的倍数+【36,100,...】(2个平方因子)的倍数...

也就是:

\sum_{i=1}^{i^2\le n} \mu(i)\left \lfloor \frac n{i^2}\right \rfloor

这样的话只需要线性筛到\sqrt{10^9}\le 40000,然后二分查找就可以了

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
2019-12-21 19:47:00
查看原题

点击跳转

i对答案会统计\left \lfloor \frac ni \right \rfloor次,但只有出现奇数次才会产生贡献

每次的贡献是i \bigoplus i+1 \bigoplus ... \bigoplus j,那么可以用数列之异或这道题的思路做

1/1
Search
search