shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共6篇）

最长树链来自专栏

前言: 之前那个博客有大问题...确实是数据太水了. 思路: 首先我们处理出4e4以内的质数,然后因为任何合数都可以写成的形式,显然大于4e4的数,假如经过这么一次筛选,一定是不会出现超过4e4的合数.对于每个数,我们处理出来它们的质因子,这里呢,用的是最原始的判断方法,假如有n个数是大质数,那么就...

思维题 dfs 数论

2021-01-11

5 1000

Numbers 来自专栏

前言: 这题难点在于复杂度分析. 实现: 首先很容易想到k假如不是质数答案为0.因为假如k不是质数,那么它一定可以写成比它小的数相乘.其次假如答案可行,必定是大于等于k的质数的乘积的形式.因为假设不是比k的质数乘积,就是利用了到的质数.这是不行的.有了这两点,暴力的代码应该是都会写的..区间的就等于...

数论

2021-01-06

3 838

List Of Integers 来自专栏

首先我们都会求[1,n]与给定的p互质的个数对吧?用容斥原理,拿n-1个p的质因子+2个p的质因子...这样容斥下去即可.题目是要求大于x第k个与p互质的数.很明显是有单调性的,我们来二分n然后ck一下,假定cnt[n]表示[1,n]与给定的p互质的个数,那么我们是要求大于x的第k个,那么我们直接拿...

二分数论

2020-09-25

5 686

质数与合数来自专栏

一个模拟题,得在自己清醒的时候打...不然就会乱坟岗..思路很简单,就是找到两个质数是不是差>(k+1),因为我们都足够聪明.那么,你下次肯定会取1(假设我是FFF),而我取k都到不了,那么我必输.其它肯定是我必胜,因为1,2,3你都不能取.所以这题就没了.但是,细节是真的多...具体看代码吧...

模拟数论

2020-08-03

1 701

Mike and gcd problem 来自专栏

挺有意思的一个题目,但是因为放在dp专题,所以在想怎么dp...还是不会dp,在网上也没找到dp的题解...至于这题性质,脑袋编译了下,但是没继续深入证明把他们全部变成偶数即是最优解...在这里阐述下证明..首先假设它们的gcd()为1.那么怎么操作才能使得方案数最小呢?先对序列进行分类分奇偶..首...

数论

2020-08-03

1 746

acwing 202题解来自专栏

代码: #include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll ksc(ll x,ll y,ll p) { ll res=0;while(y){if(y&1)res=(re...

数论

2020-06-13

1 662