zcmimi's blog

arrow_back数论共123篇文章

avatar
zc
2020-01-20 21:57:00
查看原题

点击跳转

结论:

x^{\frac14}内的因子筛掉,剩下的x一定是完全立方数或者不可化简

证明:

若存在p>x^{\frac14}b\times p^3=x,那么b>x^{\frac14}b=1

\because b>x^{\frac14} \therefore b\times p^3 >x,不符合

\therefore b=1,x为完全立方数

实现:

  1. 先晒出(10^{18})^{\frac14}(\approx31650)内的质数

  2. 筛掉x^{\frac14}内的因子,筛的过程中统计有没有立方

  3. 判断x是不是完全立方数(pow(x,1.0/3)^3+eps==x四舍五入)

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

f[i][j]表示前i个分j个邮局

f[i][j]=\min(f[x][j-1]+w[x+1][i])

满足决策单调性

avatar
zc
2020-01-06 01:03:00
查看原题

点击跳转

先考虑没有换根的操作(设根节点为1)

修改点x的权值

被影响的只有1\rightarrow x上的点,设p_1,p_2,...,p_k1\rightarrow x上的点

s_ii子树点权和

将修改看成增加v

修改后贡献为

\sum_{i=1}^k (s_{p_i}+v)^2-\sum_{i=1}^k s_{p_i}^2= k\times v^2+2v\sum_{i=1}^ks_{p_i}

我们需要预处理出s_i^2,维护s_i

考虑换根操作:

x为根,p_1,p_2,...,p_k1\rightarrow x上的点

a_i为在1为根时v_i的点权和,b_i为在x为根时v_i的点权和

可以发现a_{i+1}+b_i=a_1=b_k(因为所有点的点权和总是相同)

ans_x表示x为根时的答案

ans_x=ans_1+\sum_{i=1}^k b_i^2-a_i^2

=ans_1+\sum_{i=1}^k (a_1-a_{i+1})^2-a_i^2

=ans_1+\sum_{i=2}^k (a_1-a_i)^2-a_i^2

=ans_1+ (k-1)a_1^2- 2a_1\sum_{i=2}^k a_i

=ans_1+ s_1[(k+1)s_1-2\sum_{i=1}^k s_{p_i}]

可以使用树链剖分+(树状数组/线段树)或LCT维护

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

点击跳转

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

扩展欧拉定理

b\ge \varphi(m)时,a^b \equiv a^{(b \mod \varphi(m))+\varphi(m)} \pmod m

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

点击跳转

一道中档题-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
查看原题

点击跳转

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

点击跳转

先筛选出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

11/13
Search
search