zcmimi's blog

arrow_back欧拉函数共9篇文章

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-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
查看原题

点击跳转

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
2019-12-31 11:31:00
查看原题

点击跳转

\overbrace{88...88}^{x\text{个}8}可以表示成:

8\times \frac{(10^x-1)}9

那么8\times \frac{(10^x-1)}9=kL

8\times (10^x-1)=9kL

d=\gcd(9L,8)=\gcd(8,L)

\frac{8}d\times (10^x-1)=\frac{9L}dk

p=\frac8d,q=\frac{9L}{d}

p\times (10^x-1)=qk

\because \gcd(p,q)=1

\therefore q|(10^x-1)

\frac{9L}{d}|(10^x-1)

10^x \equiv 1 \pmod {\frac{9L}{d}}

题目中要求的是最小的解

符合欧拉定理:

\gcd(a,p)=1,那么a^{\varphi(p)} \equiv 1 \pmod p

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_i^n \sum_{j=i+1}^n gcd(i,j) \\\\ =\sum_i^n \sum_j^{i-1} gcd(i,j) \\\\ =\sum_d^n d \sum_i^n \sum_j^{i-1} [gcd(i,j)=d] \\\\ =\sum_d^n d \sum_i^{\frac nd} \sum_j^{i-1} [gcd(i,j)=1] \\\\ =\sum_d^n d \sum_i^{\frac nd} \varphi(i) \\\\ 于是欧拉筛加整除分块就可以了

本题为七倍经验题!!!

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

GCD-Extreme top: 0

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

$$

\sum{i=1}^{n-1} \sum{j=i+1}^n \gcd(i,j)

\\

= \sum_{i=1}^n g(i)

$$

$$

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

\\

= \sum{d|n}d \sum{i=1}^{n-1}[gcd(i,n)=d]

\\

= \sum{d|n}d \sum{i=1}^{\frac nd - 1}[gcd(i,n)=1]

\\

= \sum_{d|n}d \times \varphi(\frac nd);

$$

求出g的前缀和

可以用筛的方式求g

O(n \sqrt n + T);

不能用之前的套路,否则会tle

1/1
Search
search