夢に僕らで帆を張って
来るべき日のために夜を超え

标签 数学 下的文章

November 6, 2019

洛谷P4318 完全平方数

题意求第$k$个不含完全平方数因子的数数据范围:$k \le 10^9$题解二分这个数,然后验证其排名是否$\ge k$对于计算$n$以内的无平方因子数的个数,可以用到容斥原理$$ans=含0个质数的平方因子的个数-含1个质数的平方因子的个数+含2个质数的平方因子的个数 \dots$$注意到每个数的容斥系数恰好为莫比乌斯函数$\mu(i)$,上式即为$$\sum_{i=1}^{\lfloor...
November 4, 2019

洛谷P3455/POI2007 ZAP-Queries

题意求$$\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]$$数据范围:$1 \le d \le a,b \le 50000$题解假设$a\le b$$$ \begin{aligned} \sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k] &= \sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \s...
October 29, 2019

CF1225C p-binary

题意求满足$$\sum_{i=1}^x (2^k+p)=n$$的最小$x$,其中$k$为任意自然数数据范围:$1 \le n \le 10^9,-1000 \le p \le 1000$题解先移项,得$$\sum_{i=1}^x 2^k=n-xp$$在二进制下,左边能组合出$1$的数量$\le x$的任意数那么从小到大枚举这个$x$,验证即可至于枚举的上界,因为$k$为自然数($\ge 0$...
October 29, 2019

洛谷P5142 区间方差

题意给出一个数列,$2$种操作单点修改询问区间方差以上操作在$\bmod \ 10^9+7$意义下数据范围:$n,m \le 100000$题解首先方差$$\sigma^2 =\frac{1}{n} \sum_{i=1}^n (x_i-\bar{x})^2$$其中$$\bar{x}=\frac{1}{n} \sum_{i=1}^n x_i$$不满足区间和性质,将其拆开$$ \begin{al...
October 24, 2019

自适应辛普森法

自适应辛普森法一、定积分定积分是积分的一种,是函数$f(x)$在区间$[a,b]$上积分和的极限定积分的几何意义是函数的曲线上$x$的一段区间与$x$轴围成的曲边梯形的带符号面积表示为$$\int_a^b f(x)\mathrm{d}x$$由定积分的定义,若函数$f(x)$在区间$[a,b]$上可积分,则有$n$等分的特殊分法$$\lim_{n \rightarrow +\infty} \s...
October 22, 2019

洛谷P3938 斐波那契

题意求斐波那契堆的LCA数据范围:$a,b \le 10^{12}$题解性质:$f[i]$为$\le x$的最大斐波那契数,那么$x$的父亲节点为$x-f[i]$在此性质上让较大的跳到父节点,直到相等为止代码:#include<iostream> #include<cstdio> #include<algorithm> using namespace st...
October 14, 2019

CF1244C The Football Season

题意求解$$ \left\{ \begin{aligned} & wx+dy=p \\ & x+y \le n \\ & x,y\ge 0 \end{aligned} \right. $$的一组解$(x,y)$数据范围:$2 \le n \le 10^{12},1 \le p \le 10^{17},1 \le d < w...
October 12, 2019

洛谷P2613 有理数取余

题意求$c=\frac{a}{b} \bmod 19260817$的值数据范围:$0 \le a,b \le 10^{10001}$题解$$ \begin{aligned} \frac{a}{b} &= a \cdot b^{-1} \\ & \equiv (a \bmod p) \cdot (b^{-1} \bmod p) \end{aligned} $$转化为$a \ti...