zcmimi's blog

categories/刷题记录/共652篇文章

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

avatar
zc
2020-03-10 22:33:00
查看原题

点击跳转

题意:

G^{\sum d|{N\choose d}}\bmod 999911659

1 \le G \le 10^9,1 \le N \le 10^9

999911659是质数,根据欧拉定理:

G^{\sum d|{N\choose d}}\bmod 999911659 = G^{\sum d|{N\choose d} \bmod 999911658}\bmod 999911659

关键求\sum d|{N\choose d} \bmod 999911658

模数太大,直接lucas取模会炸

我们可以考虑将模数分解质因数

999911658=2\times 3 \times 4679 \times 35617

可以用lucas枚举约数算出

\begin{cases} a_1=\sum d|{N\choose d} \pmod 2 \\ a_2=\sum d|{N\choose d} \pmod 3 \\ a_3=\sum d|{N\choose d} \pmod {4679} \\ a_4=\sum d|{N\choose d} \pmod {35617} \end{cases}

然后通过crt求:

\begin{cases} x \equiv a_1 \pmod 2 \\ x \equiv a_2 \pmod 3 \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_4 \pmod {35617} \end{cases}

avatar
zc
2020-03-08 23:30:00
查看原题

点击跳转

先预处理出每次的攻击力c_i,推荐使用multiset

问题变成了:

c_ix \equiv a_i \pmod{p_i}

可是题目并没有保证a_i\le p_i

仔细阅读题目,可以发现当a_i>p_i的时候一定满足p_i=1

那么在这个情况答案就是\max_{i=1}^n(\left \lceil \frac{a_i}{c_i} \right \rceil)

接下来就是a_i \le p_i的情况了

标准的Excrt要求x的系数必须为1

我们可以转化为Exgcd解不定方程

c_ix \equiv a_i \pmod{p_i}

c_ix + p_iy = a_i

可以用Exgcd解出一组解sx,sy,并得出

x=sx+\lambda \frac{p_i}{\gcd(c_i,p_i)}

也就是

x\equiv sx \pmod{\frac{p_i}{\gcd(c_i,p_i)}}

这样就可以用Excrt求解了

特判:

  1. 所有a_i=p_i,那么所有sx=0,按照上面的方法解是不对的(答案会等于0)

    直接求出杀死每条龙所需的刀数然后所有刀数求一个lcm即可

    也就是lcm_{i=1}^n(\frac{p_i}{\gcd(c_i,p_i)})

  2. c_ip_i的倍数的时候杀不死这条龙

    但这时如果a_i=p_i,这个方程相当于没用,可以换成x \equiv 0 \pmod 1之类的

记得全部开long long,用龟速乘

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

点击跳转

avatar
zc
2020-03-08 10:57:00
查看原题

点击跳转

avatar
zc
2020-03-08 10:54:00
查看原题

点击跳转

K^x \equiv 1 \pmod M

求最小的非负整数x

最近刚学了bsgs,一眼看成exbsgs

exbsgs可以,但是比较麻烦

看到最后是1,我们可以想到欧拉定理:

K^{\varphi(M)} \equiv 1 \pmod M(\gcd(K,M)=1)

可以发现,答案是\varphi(M)的约数,那么枚举\varphi(M)的约数即可(可以一直尝试枚举删掉约数)

\gcd(K,M)!=1时无解

avatar
zc
2020-03-07 21:58:00
查看原题

点击跳转

\overbrace{111\dots111}^{\text{N个1}} \equiv k \pmod m \\ \frac{10^N-1}9\equiv k \pmod m \\ 10^N\equiv 9k+1 \pmod m

顺利地推出是bsgs,(m是质数,也就不用exbsgs了)

19/66
Search
search