何事秋。

数论只会gcd

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 数论只会gcd （共20篇）

7-3 2020 CCPC Wannafly Winter Camp Day1 C. 染色图

定义一张无向图 G=⟨V,E⟩ 是 k 可染色的当且仅当存在函数 f:V↦{1,2,⋯,k} 满足对于 G 中的任何一条边 (u,v)，都有 f(u)≠f(v)。定义函数 g(n,k) 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说，g(3,1)=0,g(3...

2020-09-04

0 406

7-1 2020 CCPC Wannafly Winter Camp Day1 A. 期望逆序对

有 n 个独立的随机变量，其中 xi 的值是一个从 [li ,ri ] 中随机选取的整数，即对于 [li ,ri ] 中的任何一个整数 j，xi =j 的概率都是 (ri −li +1)−1 。现在你需要给出一个长度为 n 的排列 p，那么可以得到一...

2020-09-04

0 575

7-8 2020 CCPC Wannafly Winter Camp Day1 H. 最大公约数

这是一道钓鱼小王子，秒出的题，至今我也不会证明。有三个人，A,B,C，其中 A 和 B 共享了一个神秘的数字 k，已知 1≤k≤n。现在 A 和 C 说：“k 的值等于 x”。 C 不太信任 A，于是想向 B 确认一下 k 是否真的等于 x。B 虽然不想直接把 k 的值告诉 C，但是 B 允...

2020-09-04

0 401

P2261 [CQOI2007]余数求和（数论分块）

题目链接题面：题解：代码： #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include&l...

2020-09-04

0 507

P1403 [AHOI2005]约数研究（数论分块）

题目链接题面：题解：考虑因子x在1–n中出现的次数为n/x 枚举因子，数论分块。代码： #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #in...

2020-09-04

0 454

P1414 又是毕业季II （约数）

题目链接题面：题解：统计每个因数出现的次数。对于每个出现次数维护最大的因数。逆向更新代码： #include<iostream> #include<cstdio> #include<cstring> #include<cmath>...

2020-09-04

0 505

P1249 最大乘积（数论、贪心）

题目链接题面：题解：从2开始连续几个自然数的乘积最大。假设我们 2+3+4+…+k>=n 刚好成立。我们设ans=2+3+4+…k 如果ans=n，我们直接输出乘积即可。如果ans-n=1，那我们去掉2，令k+1 如果ans-n>1 假设 ans-n=p，那么我们去掉p...

2020-09-04

0 699

P1338 末日的传说（逆序对）

题目链接题面：题解：如何让逆序对数为m的序列字典序最小呢？假设位置p是最后一个原始序列的位置，那这个点应该尽量靠右，才能使得字典序最小。而为了保证有m个逆序对，要求p后面的逆序对数尽量大。需要降序排列。这样问题就转成找点p，同时在找到p时还需要知道 m-后面所有逆序对数剩余的值...

2020-09-04

0 467

2020牛客暑期多校训练营（第一场）J、Easy Integration （数学、分部积分）

题目链接题面：题意：求给定的定积分。题解，化成 ∫ xn (1-x)n dx 然后用分部积分法即可得。分部积分法：∫ udv = uv - ∫ vdu 最终为 n！/（（n+1）*（n+2） * … * (2n+1) ）代码： #include<iostream>...

2020-09-04

0 540

2020牛客暑期多校训练营（第四场）B、Basic Gcd Problem （线性筛）

题目链接题面：题解：我们可以知道 f c i ...

2020-09-04

0 835