Deep_Dark_FAntasy♂

基本数论、组合...

Codeforces(3) 博弈论(3) 并查集(2) 数据结构(2) 未归档(176) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 基本数论、组合数学（排列组合，容斥等）（共14篇）

模线性方程组

模线性方程组题目链接：http://poj.org/problem?id=2947有m条记录，n个零件，那么就是m个方程，n个未知数，然后所花的天数和在工厂呆的天数对7同余，也就是求解一个模线性方程组。代码： #include<bits/stdc++.h> #define MAXN 31...

模线性方程组板子

2020-09-04

1 452

EXTENDED LIGHTS OUT

题目链接：http://poj.org/problem?id=1222就是亮灯问题56的灯，列30个方程，异或方程组一套板子，完事*代码：** #include <iostream> #include <stdio.h> #include <string.h&g...

板子方程异或

2020-09-04

1 440

CCPC2016 B.异或方程组高斯消元板子题 Zhu and 772002

题目连接：https://vjudge.net/contest/392610#problem/B解题思路：对于每个质因子，显然只有偶数和奇数的两种情况需要考虑，考虑构建异或方程组。高斯消元法一个板子下来，求出自由未知元的个数，然后就是对自由元赋值，0或者1，总共有2^k种，别忘了去掉全是0的情况，因...

异或方程高斯消元板子

2020-09-04

1 453

E-Groundhog Looking Dowdy(欧拉降幂，质因子) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5674/E思路：对于x，y的公共质因子p来说，如果在x的唯一分解中的幂次为m，在y的唯一分解中的幂次为n那么当mi >= nj的时候，即j <= mi/n的时候，gcd的p的幂次为nj当mi < ...

质因子欧拉降幂

2020-08-09

1 527

Basic Gcd Problem 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5669/B解题思路：我们可以直接看出当x每次都只去掉一个质因子，fc=c^(x的素因子个数)，本题T是1e6因此直接欧拉筛打表好了，维护一下素因子个数。代码： #include<bits/stdc++.h>...

欧拉筛维护素因子个数

2020-07-23

1 471

洛谷P1919 【模板】A*B Problem升级版（FFT快速傅里叶）

刚学完FFT，拿来连练手题目链接：https://www.luogu.com.cn/problem/solution/P1919解题思路：FFT是解决多项式乘法的，想办法把数给变成多项式比如：有了这个处理以后，我们可以直接看出来数的乘法不就是多项式乘法吗？！代码中有些细节问题已做出注释代码： #in...

FFT 大数乘法

2020-07-15

1 540

(莫比乌斯)小A的数学题

题目链接：https://ac.nowcoder.com/acm/problem/23616解题思路：O(nm)算法超时，使用莫比乌斯反演把时间复杂度降低成线性。目前做的题目当中，要使用莫比乌斯反演的题目通常是答案是关于gcd的题目且数据规模大，暴力卒。*推导过程：** 代码： #include&...

莫比乌斯反演 gcd

2020-07-12

1 812

莫比乌斯反演

通过电子科技大学ACM集训队的视频学习了莫比乌斯反演本篇内容为学习笔记题目引入：给定整数N和M。求满足1<=x<=N, 1<=y<=M,且gcd(x,y)为质数的点对(x,y)的个数。数据范围：1<=N,M<=1,000,000 目录：1.莫比乌斯函数2.莫比...

狄利克雷卷积大数莫比乌斯反演 gcd 积性函数整除分块莫比乌斯函数杜教筛

2020-07-08

0 550

素数判断

先看题目：https://ac.nowcoder.com/acm/problem/14399解题思路：因为数据量并不大( ),所以用试除法(O(√n))不会超时代码： #include<bits/stdc++.h> using namespace std; int factor[110]...

素因子素数判断试除法

2020-06-29

0 508

(大数分解质因子)Pollard's rho 算法

算法思想基本思路：对于给定的一个整数 n，显然如果 n 为素数（Miller-Rabin 算法判断），那么算法结束，返回唯一素因子 n。否则，pollard's rho 算 ***试着找到 n 的一个因子 a（a 并不一定是素数），然后递归 Pollard_rho( a ) 和 Pollard_...

Pollard_rho算法大数分解质因子

2020-06-29

1 2401