[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M

题目链接

题意:

求 $$\sum_{k=1}^{N}((kM)\& M)mod(10^9+7)$$

其中 $1 \le N \le 10^{18}$ , $1 \le M \le 10^{11}$

题解:

按位来做,考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算,比如当前处理的是第i位 ,就可以写成 $$\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^i} \rfloor)-2*\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^{i+1}} \rfloor)$$
这显然是一个类欧几里得的模板式子,我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M”

[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query

题目链接

题意:

给定 $N$ 个数字, $Q$ 次询问,每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$

题解:

首先一个重要的结论:以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明:每次往原有的序列里加入一个数字的话, $gcd$ 要么不变,要么至少变为原来的1/2,因此为指数级减小。

有了这个结论,我们可以试着来枚举一个端点考虑本题,不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ,那么要求出以$r_j$为结尾的所有 $gcd$ ,只需遍历S中的每个数字$d_k$,计算其与$a_j$ 的 $gcd$ ,放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果,表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。

现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取,由上面的结果可以试着考虑能否转化为前缀问题。可以发现,如果我们对所有的$[l,r]$离线处理,按$r$从小到大排序,并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话,每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l,这句话具体的意思是,一个 $gcd$ 可能出现过了很多次,不同的段都可以得到这个 $gcd$ ,但是我们只考虑这些段中左端点l_j最大的那个点$p_j$,这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ (种类+1),这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”

[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II

去年校赛的时候感觉此题难的一批,,,昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟。。。Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了。

这个题的思想就是:把每一列3*1的小方格当成一个“珠子”,把他可能的8种情况当成“颜色”,然后这些颜色同时也代表状态,类似于poj2888的颜色相邻限制,这里的状态之间“能不能相邻”其实就是在状压dp里“能不能转移”的限制,不同状态之间的转移图如下(来自matrix67的那篇文章

继续阅读“[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II”

[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci

主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩,只见过两次应用这个题目的情况,一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时,称“d是模p的二次剩余”,当对任意不成立时,称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质:
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”

[二维DP][组合计数][利用对称性简化问题] UVALive 3295

https://vjudge.net/problem/UVALive-3295

这个题目和3720很像,尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息,或者可以这么说,按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题,按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线,但是算的是“所有的斜率为正”的斜线,也就是覆盖了每一种情况,那么剩下的情况其实只有水平竖直和斜率为负的斜线,但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等,因此只需要*2即可,而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线,其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是,在gcd的算法中如果a和b有一个数字为0那么返回值就会是0,这种情况在这里的递推过程中是会出现问题的,需要注意让循环从2开始,也算是一个小小的坑吧。。以前没有注意到。

继续阅读“[二维DP][组合计数][利用对称性简化问题] UVALive 3295”

[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways

很有意思的一个组合数学题。

整个题的最核心的思想就是,两个线段共线的判断!只要有两个点就可以确定一条线段(直线),那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了!所以两种算法的思想都在于一个2

第一种方法:最纠结的问题还是在于,怎么去重。想到了枚举角度的方法却没有想到怎么去重,还是思维不行。第一种方法是每次枚举所有可能的矩形,然后计算对角线的数量,这个很好算也就是有多少个矩形,直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况,这种情况一定说明这种对角线的角度第一次出现(因为我们从小到大枚举i和j),所以对答案贡献为正,还有一种情况是gcd(i,j)==2,这说明之前已经出现过了这种对角线,所以这里要减去对应的数量,注意这里是最重要的:减去的是对应的数量,然后其他的gcd值不用+也不用-。原因就在于,如果你有一个4*4的或者3*3的矩形对角线重算了,那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线!因为这个2会按照不同的起始点一直推下去。 继续阅读“[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways”

[数论][暴力][分段] UVA 11754 Code Feat

之所以写这个题是因为他提供了一种新的解决问题的思路。。两个暴力算法结合起来竟然就不暴力了。。

首先直接暴力枚举每个set里的余数然后解同余方程组可以得到一个Πki复杂度的算法,但是这个在k太大的时候会爆,然后k很大的时候就用了同余方程的另一种暴力解法,找到一个同余方程枚举他的所有解然后去判断其他的等式是否满足。。。这个在k比较大的时候比较快(但是感觉这俩算法组合还是有点看RP
代码基本上都是抄的书上就这。不过调了下LIMIT的范围发现从100到500000都可以过。。

继续阅读“[数论][暴力][分段] UVA 11754 Code Feat”

[数学][大整数质因数分解] codeforces1033D Divisors

思路简单,就是求出来结果的所有质因数的指数+1乘起来就行了。

首先由于题目的要求这里读入的ai只有两种情况,要么ai=p*q是两个不相等素数的乘积,要么ai=p^k,其中k取2,3,4。显然后一种情况很容易处理,但是第一种就有些难受了,直接的想法是用一些优秀的O(N^(1/4))的非完美大整数分解算法(这个看tutorial的评论区神仙各有千秋)。但是由于第一类的数只能分解成两个质因数,而且我们最后要的是质因数的指数而不需要关心质因数本身是多少,所以就有了更好的策略:如果一个数字的质因数在其他数字中出现过,那么一定可以通过gcd求出来,这时候等于说另一个质因数直接一除也能求出来,等于这个ai就完全解决了,像第二种情况一样加到map里即可;如果说这个数的俩质因数都没有在其他数字中出现过那么我们肯定不能求出来这俩数字是多少了,但是我们可以知道出现了俩独特的质因数,他出现且仅出现在所有aj==ai里,那么我们可以把ai直接存进map里,存起来他对应的加了多少次,另外要单独开一个set记录下来哪些ai是这样的ai,最后计算的时候如果是这样的ai的话就乘以(1+map值)的平方就可以了。

所以说一定要分析所给数据的性质,他的约束是解题的难点但同时也可能是解题的突破口。
写的时候还有一点弄错了就是把哥德巴赫猜想和这个搞混了。。那个是+这个是*,而且哥德巴赫猜想在1e18的范围内一定是有一个小的和一个大的,这个小的不超过1e5好像,所以那个是只需要枚举小的然后判断大的是否为质数即可。

继续阅读“[数学][大整数质因数分解] codeforces1033D Divisors”