下沙做网站软件,西安工商注册网上平台,中国工业品网,衡水网站建设集团problem
codeforces
对于给定的正整数 l≤l\leql≤#xff0c;定义 c(l,r)c(l,r)c(l,r) 为满足下列条件的正整数对 (i,j)(i,j)(i,j) 的数量#xff1a; l≤i≤j≤rl\leq i\leq j\leq rl≤i≤j≤r#xff1b;gcd(i,j)≥l\gcd(i,j)\geq lgcd(i,j)≥l。
给定正整数 k≤nk\…problem
codeforces
对于给定的正整数 l≤l\leql≤定义 c(l,r)c(l,r)c(l,r) 为满足下列条件的正整数对 (i,j)(i,j)(i,j) 的数量
l≤i≤j≤rl\leq i\leq j\leq rl≤i≤j≤rgcd(i,j)≥l\gcd(i,j)\geq lgcd(i,j)≥l。
给定正整数 k≤nk\leq nk≤n。
对所有满足 0x1x2⋯xkxk1n0x1x2⋯xkxk1n0x1x2⋯xkxk1n 的整数序列 (x1,...,xk1)(x_1,...,x_{k1})(x1,...,xk1)
计算 ∑i1kc(xi1,xi1)\sum_{i1}^kc(x_i1,x_{i1})∑i1kc(xi1,xi1) 的最小值。
你需要回答 TTT 组询问。
对全部数据1≤T≤3×1051\leq T\leq 3\times 10^51≤T≤3×1051≤k≤n≤1051\leq k\leq n\leq 10^51≤k≤n≤105。
solution
先设 f(i,k):f(i,k):f(i,k): 枚举到 iii 一共划分了 kkk 个组的最小值。
则有转移 f(i,k)minj≤i{f(j−1,k−1)c(j,i)}f(i,k)\min_{j\le i}\Big\{f(j-1,k-1)c(j,i)\Big\}f(i,k)minj≤i{f(j−1,k−1)c(j,i)}。
但遗憾的是时间空间双双起飞而且空间并不能滚动掉。
不妨挖掘一下 c(l,r)c(l,r)c(l,r) 的性质
ovservation1:\text{ovservation1}:ovservation1: c(l,r)≥r−l1c(l,r)\ge r-l1c(l,r)≥r−l1。显然至少每个 i∈[l,r],(i,i)i\in[l,r],(i,i)i∈[l,r],(i,i) 点对就能提供一次贡献。observation2:c(i,2i−1)i\text{observation2}:c(i,2i-1)iobservation2:c(i,2i−1)i。显然 [i,2i−1][i,2i-1][i,2i−1] 中的任意两个数的 gcdi\gcdigcdi。
基于以上两个观察不难得出当 n2kn2^kn2k 时答案一定为 nnn。
因为我们有足够多的组数可以分成形如 c(i,2i−1)c(i,2i-1)c(i,2i−1) 的形式。
所以我们状态设计的第二维就可以降成 log\loglog 级别。空间问题已经被解决了。
接下来考虑时间复杂度其直接挂钩于优化 c(l,r)c(l,r)c(l,r) 的计算。 c(l,r)∑ilr∑jir[gcd(i,j)≥l]∑dlr∑ilr∑jir[gcd(i,j)d]∑dlr∑i⌈ld⌉⌊rd⌋∑ji⌊rd⌋[gcd(i,j)1]∑dlr∑i1⌊rd⌋∑ji⌊rd⌋[gcd(i,j)1]∑dlr∑j1⌊rd⌋∑i1j[gcd(i,j)1]∑dlr∑i1⌊rd⌋φ(i)c(l,r)\sum_{il}^r\sum_{ji}^r[\gcd(i,j)\ge l]\sum_{dl}^r\sum_{il}^r\sum_{ji}^r[\gcd(i,j)d]\\ \sum_{dl}^r\sum_{i\lceil\frac{l}{d}\rceil}^{\lfloor\frac rd\rfloor}\sum_{ji}^{\lfloor\frac rd\rfloor}[\gcd(i,j)1]\sum_{dl}^r\sum_{i1}^{\lfloor\frac rd\rfloor}\sum_{ji}^{\lfloor\frac rd\rfloor}[\gcd(i,j)1]\\ \sum_{dl}^r\sum_{j1}^{\lfloor\frac rd\rfloor}\sum_{i1}^j[\gcd(i,j)1]\sum_{dl}^{r}\sum_{i1}^{\lfloor\frac rd\rfloor}\varphi(i) c(l,r)il∑rji∑r[gcd(i,j)≥l]dl∑ril∑rji∑r[gcd(i,j)d]dl∑ri⌈dl⌉∑⌊dr⌋ji∑⌊dr⌋[gcd(i,j)1]dl∑ri1∑⌊dr⌋ji∑⌊dr⌋[gcd(i,j)1]dl∑rj1∑⌊dr⌋i1∑j[gcd(i,j)1]dl∑ri1∑⌊dr⌋φ(i) 记 S(n)∑i1nφ(i)S(n)\sum_{i1}^n\varphi(i)S(n)∑i1nφ(i)即 φ(i)\varphi(i)φ(i) 的前缀和。则 c(l,r)∑ilrS(⌊ri⌋)c(l,r)\sum_{il}^rS(\lfloor\frac ri\rfloor)c(l,r)∑ilrS(⌊ir⌋)。
O(n)O(n)O(n) 线性筛预处理 φ(i),S(i)\varphi(i),S(i)φ(i),S(i) 后可以数论分块做到 O(r−l1)O(\sqrt{r-l1})O(r−l1) 计算。
考虑进一步地优化转移。
kkk 只与 k−1k-1k−1 挂钩。所以状态转移的时候不妨先枚举 kkk 再枚举 iii。
对于固定的 kkk我们简化内层转移写成 f(i)minj≤i{f(j−1)c(j,i)}f(i)\min_{j\le i}\Big\{f(j-1)c(j,i)\Big\}f(i)minj≤i{f(j−1)c(j,i)}。
看见这种形式的转移方程我们 打表验证 大胆猜测是决策单调性的。 证明 c(l,r)c(l,r)c(l,r) 区间包含单调性。 即 ∀l≤l′≤r′≤r\forall\ l\le l\le r\le r∀ l≤l′≤r′≤r 有 c(l′,r′)≤c(l,r)c(l,r)\le c(l,r)c(l′,r′)≤c(l,r)。根据 c(l,r)c(l,r)c(l,r) 的定义显然。 证明 c(l,r)c(l,r)c(l,r) 满足四边形不等式交叉小于包含。 即 ∀l1l2r1r2\forall\ l_1l_2r_1r_2∀ l1l2r1r2 有 c(l1,r1)c(l2,r2)≤c(l1,r2)c(l2,r1)c(l_1,r_1)c(l_2,r_2)\le c(l_1,r_2)c(l_2,r_1)c(l1,r1)c(l2,r2)≤c(l1,r2)c(l2,r1)。 c(l1,r2)c(l2,r1)∑il1r2S(⌊r2i⌋)∑il2r1S(⌊r1i⌋)∑il1l2−1S(⌊r2i⌋)∑il2r2S(⌊r2i⌋)∑il1r1S(⌊r1i⌋)−∑il1l2−1S(⌊r1i⌋)∑il1l2−1(S(⌊r2i⌋)−S(⌊r1i⌋))∑il2r2S(⌊r2i⌋)∑il1r1S(⌊r1i⌋)∑il1l2−1(S(⌊r2i⌋)−S(⌊r1i⌋))c(l2,r2)c(l1,r1)c(l_1,r_2)c(l_2,r_1)\sum_{il_1}^{r_2}S(\lfloor\frac{r_2}{i}\rfloor)\sum_{il_2}^{r_1}S(\lfloor\frac{r_1}{i}\rfloor)\\ \sum_{il_1}^{l_2-1}S(\lfloor\frac{r_2}{i}\rfloor)\sum_{il_2}^{r_2}S(\lfloor\frac{r_2}{i}\rfloor)\sum_{il_1}^{r_1}S(\lfloor\frac{r_1}{i}\rfloor)-\sum_{il_1}^{l_2-1}S(\lfloor\frac{r_1}{i}\rfloor)\\ \sum_{il_1}^{l_2-1}\Big(S(\lfloor\frac{r_2}{i}\rfloor)-S(\lfloor\frac{r_1}{i}\rfloor)\Big)\sum_{il_2}^{r_2}S(\lfloor\frac{r_2}{i}\rfloor)\sum_{il_1}^{r_1}S(\lfloor\frac{r_1}{i}\rfloor)\\ \sum_{il_1}^{l_2-1}\Big(S(\lfloor\frac{r_2}{i}\rfloor)-S(\lfloor\frac{r_1}{i}\rfloor)\Big)c(l_2,r_2)c(l_1,r_1) c(l1,r2)c(l2,r1)il1∑r2S(⌊ir2⌋)il2∑r1S(⌊ir1⌋)il1∑l2−1S(⌊ir2⌋)il2∑r2S(⌊ir2⌋)il1∑r1S(⌊ir1⌋)−il1∑l2−1S(⌊ir1⌋)il1∑l2−1(S(⌊ir2⌋)−S(⌊ir1⌋))il2∑r2S(⌊ir2⌋)il1∑r1S(⌊ir1⌋)il1∑l2−1(S(⌊ir2⌋)−S(⌊ir1⌋))c(l2,r2)c(l1,r1) 显然 ∑il1l2−1(S(⌊r2i⌋)−S(⌊r1i⌋))≥0\sum_{il_1}^{l_2-1}\Big(S(\lfloor\frac{r_2}{i}\rfloor)-S(\lfloor\frac{r_1}{i}\rfloor)\Big)\ge0∑il1l2−1(S(⌊ir2⌋)−S(⌊ir1⌋))≥0所以 $ c(l_1,r_2)c(l_2,r_1)\ge c(l_1,r_1)c(l_2,r_2)$ 得证。
所以 f(i)f(i)f(i) 是具有决策点单调的性质的。经典 1D1D\text{1D1D}1D1D 类单调性优化。 证明 f(i)f(i)f(i) 具有决策单调性。 即设 g(i)g(i)g(i) 为 iii 的最佳转移决策点则 ∀jig(j)≤g(i)\forall_{ji}\ g(j)\le g(i)∀ji g(j)≤g(i)。 设 yxjiyxjiyxji且 f(j)f(j)f(j) 的最佳决策点为 xxx。则有 f(x−1,j)c(x,j)≤f(y−1,j)c(y,j)f(x-1,j)c(x,j)\le f(y-1,j)c(y,j)f(x−1,j)c(x,j)≤f(y−1,j)c(y,j)。c(y,j)c(x,i)≤c(y,i)c(x,j)c(y,j)c(x,i)\le c(y,i)c(x,j)c(y,j)c(x,i)≤c(y,i)c(x,j)。 两式相加有f(x−1)c(x,j)c(y,j)c(x,i)≤f(y−1)c(y,j)c(y,i)c(x,j)f(x-1)c(x,j)c(y,j)c(x,i)\le f(y-1)c(y,j)c(y,i)c(x,j)f(x−1)c(x,j)c(y,j)c(x,i)≤f(y−1)c(y,j)c(y,i)c(x,j)。 化简后有f(x−1)c(x,i)≤f(y−1)c(y,i)f(x-1)c(x,i)\le f(y-1)c(y,i)f(x−1)c(x,i)≤f(y−1)c(y,i)。 所以对于 iii 而言最佳决策点选 xxx 一定优于/不劣于选 yyy。
那么我们就对于外层枚举的每一个 kkk跑决策点的分治。
(l,r,L,R)(l,r,L,R)(l,r,L,R) 处理 i∈[l,r]i\in[l,r]i∈[l,r] 的最优决策点落在 [L,R][L,R][L,R] 区间内。
midlr2mid\frac{lr}2mid2lr先算出 c(R1,mid)c(R1,mid)c(R1,mid)然后 c(i,mid)c(i1,mid)S(⌊midi⌋)c(i,mid)c(i1,mid)S(\lfloor\frac{mid}{i}\rfloor)c(i,mid)c(i1,mid)S(⌊imid⌋)。
再从 min(mid,R)\min(mid,R)min(mid,R) 开始 →L\rightarrow L→L 枚举 midmidmid 的最佳决策点。
因为最佳决策点编号必须小于自己编号。
再根据 midmidmid 分成左右并把决策点区间分成左右。
复杂度额额额约莫 O(nTknnlogn)O(nTkn\sqrt{n}\log n)O(nTknnlogn)。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 100005
int T, n, cnt;
int prime[maxn], phi[maxn], vis[maxn], S[maxn];
int f[maxn][20];void sieve( int n 1e5 ) {phi[1] 1;for( int i 2;i n;i ) {if( ! vis[i] ) prime[ cnt] i, phi[i] i - 1;for( int j 1;j cnt and i * prime[j] n;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {phi[i * prime[j]] phi[i] * prime[j];break;}else phi[i * prime[j]] phi[i] * phi[prime[j]];}}for( int i 1;i n;i ) S[i] S[i - 1] phi[i];
}int calc( int l, int r ) {int ans 0;for( int i;l r;l i 1 ) {i min( r / ( r / l ), r );ans S[r / l] * ( i - l 1 );}return ans;
}void solve( int l, int r, int L, int R, int k ) {if( l r ) return;int mid l r 1;int sum calc( R 1, mid );int ans 1e18, pos;for( int i min( R, mid );i L;i -- ) {sum S[mid / i];if( sum f[i - 1][k - 1] ans )ans sum f[i - 1][k - 1], pos i;}f[mid][k] ans;solve( l, mid - 1, L, pos, k );solve( mid 1, r, pos, R, k );
}signed main() {for( int i 1;i 1e5;i ) f[i][1] i * (i 1) 1;sieve();for( int k 2;k 17;k ) solve( 1, 1e5, 1, 1e5, k );scanf( %lld, T );while( T -- ) {int k;scanf( %lld %lld, n, k );if( k 17 or (1 k) n ) printf( %lld\n, n );else printf( %lld\n, f[n][k] ); }return 0;
}
