zcmimi's blog

arrow_back数论共123篇文章

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

点击跳转

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

点击跳转

前置定理:

d(ij) = \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1]

所以:

n<m

\sum_{i=1}^n \sum_{j=1}^m d(ij) \\ =\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1] \\ =\sum\limits_{x=1}^n\sum\limits_{y=1}^m \left\lfloor\frac{n}{x}\right\rfloor \left\lfloor\frac{m}{y}\right\rfloor [\gcd(x,y)=1]

x、y换成i、j

\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1] \\ =\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor \sum_{k|gcd(i,j)}\mu(k)

g(i)=\sum_{i=1}^n \left \lfloor \frac ni \right \rfloor

ans=\sum_{k=1}^n\mu(k) g(\left \lfloor \frac nk \right \rfloor) g(\left \lfloor \frac mk \right \rfloor) \\

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

点击跳转

一道中档题-Factorial top: 0

观察一下,

一个数在k进制下有多少个后缀0,就是一个数能整除k多少次

那么先把k分解质因数,并求出每个质因数的个数,存到数组里面

要怎么算出n!里面有多少个质因数?

p(p是质数)个数里面有一个p,这些数是p^1,p^2,...p^x,这些数中每p个数中又有一个p,那我们这样一直循环下去就可以求出质因数的个数,然后在除以他们在k中出现的次数,然后取min就是答案

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

点击跳转

$$ \frac{1}{n}\sum_{i=1}^{n}(a_i-\bar a)^2

\\

= \frac 1n \sum_{i=1}^{n}(a_i^2-2\bar a\times a_i+{\bar a}^2)

\\

= \frac 1n (\sum_{i=1}^nai^2 - 2\bar a\sum{i=1}^n a_i + n \bar a^2)

\\

= \frac 1n \sum_{i=1}^n a_i^2 - \bar a^2 $$

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

点击跳转

先筛选出d_a,d_b,d_c

如果a,b,c的约数都不相同,那么ans = d_a \cdot d_b \cdot d_c

我们来考虑要减去的部分

(a,b,c) , (b,a,c)这样的是不符合的,减去其中一个

也就是减去d(gcd(a,b))\times(d(gcd(a,b)-1))

同理,(a,c,b),(c,b,a)也要减去.

这样的话会多减了一个d(gcd(a,b,c))*(d(gcd(a,b,c))-1),要加回来

...

https://www.luogu.com.cn/blog/lingchi/solution-cf1008d

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

点击跳转

我们假设现在要合并的两个数是x,y,那么合并后是x\cdot10^{\ln y+1}+y

我们可以预处理出 a_i \cdot 10^t \mod k(t\le 10)

每个a_i统计有多少个数接到它前面符合要求

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

点击跳转

有趣的题

我们可以发现只有一组相邻两数只能求差的绝对值,其他数都可以取绝对值求和

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

点击跳转

$$ (a_i+a_j)(a_i^2+a_j^2)\equiv k \mod p \\ (a_i + a_j) \times (a_i - a_j) \times (a_i^2 + a_j^2) \equiv k(a_i - a_j) \mod p

\\

(a_i^2 - a_j^2) \times (a_i^2 + a_j^2) \equiv k(a_i - a_j) \mod p

\\

a_i^4 - a_j^4 \equiv ka_i - ka_j \mod p

\\

a_i^4 - ka_i \equiv a_j^4 - ka_j \mod p

$$

那么只要把(a_i^4 - ka_i) \mod p放到桶里就可以知道有多少个数符合

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

点击跳转

我们可以发现如果p\le x,那么x\mod p \le \frac x2

所以取模最多\log x

记录区间最大值,如果小于p那么直接返回

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

12/13
Search
search