RainAir
My OI Blog
RainAir

数论
文章归档

「BZOJ1129」Per

题意:给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m 不保证 $m$ 是质数。 题解:我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个,不难发现题目要求的是: $$\sum_{i=1}^n \frac{(n-i)!}{\Pi_j cnt_j} (\sum_{j < s_i}cnt_j)$$ 显…

   169   2019-08-18   169 去吊打作者

「CF1106F」Lunar New Year and a Recursive Sequence

题目链接 首先 $f_{[1\cdots k-1]} = 1$,所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。 我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解,然后就是解方程 $$f_k^e \equiv m (\mod 998244353)$$ 了。 这是一个简单的离散对数入门题,我们就两边取个 $log_g$ $$(lo…

   243   2019-08-01   243 去吊打作者

「ZROI851」exexBSBSGSGS

题意:求$a^x \equiv b(\mod p^e)$ 的最小整数解。 $3 < p \leq 50,p^e \leq 10^18,a\nmid p,b \nmid p$,询问不超过 $1000$ 组。 暴力分跑 bsgs 其实就可以了...因为保证了 $(a,p^e) = 1$。 但是这样显然会 T,于是我们就不要往 bsgs 的方面去想了。 我们考虑 $p$…

   286   2019-07-21   286 去吊打作者

简单数论公式

记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑 整除与不定方程 $d|a,d|b \Leftrightarrow d|(a-b)$ 证明:$a = pd,b = qd,a-b = (p-q)d$ 2. $(a,b)|d \Leftrightarrow ax+by = d$ 存在整数解。 证明: 从右往左推:令 $g=(a,b)$,则有 $…

   217   2019-07-18   217 去吊打作者

「BZOJ5028」小Z的加油店

题目描述 题目链接 小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子,每个瓶子有一个容量vi。每次别人来加油,他会让 别人选连续一段的瓶子。他可以用这些瓶子装汽油,但他只有三种操作: 1. 把一个瓶子完全加满; 2. 把一个瓶子完全倒空; 3. 把一个瓶子里…

   518   2018-11-24   518 去吊打作者

杜教筛学习笔记

预备知识 杜教筛是一种能在比线性复杂度还优秀的复杂度中处理处积性函数的前缀和。 主要运用 Dircichlet 卷积来完成复杂度的化简。 定义 设 $ f(n) $ 为一个数论函数,$ S(n) = \Sigma_{i=1}^nf(i)$。 我们考虑再找到一个合适的数论函数 $g(i)$,使得 $$ \Sigm…

   422   2018-08-17   422 去吊打作者
标签
近期评论