威风镰鼬

题解

/ 注册

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

题解 | #集合中的质数#

思路考察容斥定理。质因子最多20个，所以我们可以状压一下，枚举每次选定因子的情况。考虑只有一个因子pri的情况下，1~m个数中总共由m/pri个，那么下一次选定两个因子p1,p2时，就要减去m/(p1*p2)个，加减取决于选定因子的个数。代码 #include<bits/stdc++.h&...

状压位运算数论

2021-11-25

3 406

题解 | #托米的游戏#

思路对于每个节点来说，对答案的期望贡献都是其深度的倒数。因此，我们只要将每个点贡献累加就能得到最终期望。用快速幂求每个贡献(1dep[i]\frac{1}{dep[i]}dep[i]1)的逆元，再相加就是最终答案。代码 #include<bits/stdc++.h> #defin...

数学概率数论

2021-11-25

2 525

题解 | #黑猫的小老弟#

思路小老弟树产生的分数都是互质的，由于题目规定第n行产生的分子分母不超过n,而且经过简单推导可以猜测第n代可以表示出分子分母不超过n的所有互质对，那么我们就可以用欧拉函数来做。直接规定第n代产生的数就是欧拉函数的n行前缀和。代码 #include<bits/stdc++.h> #de...

数论

2021-11-25

2 491

题解 | #阶乘分解#

思路我们普通求阶乘的时候，边乘边除质数，就可以保证不爆范围。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e6+7; ...

数论

2021-11-24

1 420

题解 | #约数个数的和#

思路对数论初学者来说可能有点困难，但想通了会觉得相当简单。我们考虑每个数是多少个数的约数，然后贡献到答案中即可，那么对于n个数，数字p是n/p个数的约数，答案直接加上即可。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #def...

数论

2021-11-24

3 426

题解 | #H(n)#

思路数论分块模板，式子res=(res+n/i)的i枚举时会超时，注意到n/i的结果会有连续的一段相等，我们使用数论分块，直接返回每一段的答案。对于常数n，使得式子[ni]=[nj][\frac{n}{i}]=[\frac{n}{j}][in]=[jn]成立的最大的满足的i≤j≤n的j的值为...

C++ 数论分块暴力

2021-11-18

1 333

题解 | #Football#

思路我们采用动态规划的思想，从每一轮出发，计算每支队伍这轮获胜的概率。基于全概率公式，队伍概论胜利的概率可以由对阵其他可以打的队伍获胜的概率之和。现在问题就是如何表示该轮可对阵的队伍：假设由2^n只球队，如果j在[0,2^(n-1)]里面，k在[2^(n-1)+1,2^n]里面，那么很明显他们要在...

动态规划数论概率dp

2021-08-20

1 384

题解 | #[SDOI2011]计算器#

思路询问1：快速幂就可以了。询问2：可以转化为求解同余方程，使用扩展欧几里得就可以求解，在gcd(y,p)|z的时候有解。询问3：重点要讲的BSGS算法(我习惯叫北上广深)。我们要求满足同余式的最小非负数x，暴力枚举x在[0,p)的范围内，在p非常大的情况下是会爆的。可以令x=mi-j，那么式子转...

快速幂 BSGS 扩展欧几里得数论

2021-08-13

1 477

题解 | #Visible Lattice Points#

思路没学过数论的同学估计一开始是不会想到欧拉函数的。那么我们怎么去联想到这东西呢。这道题，我们只需要计算y>x的点（上三角），然后答案就是2*ans+1了。(上三角+下三角+斜率为1的点)我们现在通过找规律来看看n不同时斜率的一个情况(y/x):n=1,ans=0;n=2,ans=1,k=1...

欧拉函数数论

2021-08-12

1 573

题解 | #Biorhythms#

思路在信息学奥赛数论一本通里面我愣是没搞懂题解的5544、14421、1288这些数是怎么来的，在网上找了很多博客才搞懂中国剩余定理的原理。总结一下步骤：（方程组形式为mod m意义下与a同余）求大模数M->对每个小模数M/m，求模m意义下的逆元i，那么M/mia就是满足方程的一个最小数，然...

数论中国剩余定理

2021-08-05

1 392