(N)为上确界,(n)为(a)数组元素个数,(D)为约数个数。
方法一
(1.)求出(d),(d[i])表示(i)的所有约数(有序)。
时间复杂度:(O(NlogN))
vector d[N + 1];
for (int i = 1; i
(2.)求出(f),(f[i])表示满足(gcd=ki)的无序对的数量,(kinmathbb{N^+})。
在遍历到第(j)个数时,(cnt[i])表示前(j-1)个数含有约数(i)的个数。
时间复杂度:(O(nD))
vector f(N + 1);
vector cnt(N + 1);
for (int j = 1; j
(3.)容斥定理更新(f),此时(f[i])表示满足(gcd=i)的无序对的数量。
时间复杂度:(O(NlogN))
for (int i = N; i; i--)
for (int j = 2 * i; j
总时间复杂度:(O(NlogN+nD))
方法二
(1.)求出(f),(f[i])表示满足(gcd=ki)的无序对的数量,(kinmathbb{N^+})。
时间复杂度:(O(NlogN))
vector f(N + 1);
for (int i = 1; i
(2.)容斥定理更新(f),此时(f[i])表示满足(gcd=i)的无序对的数量。
时间复杂度:(O(NlogN))
for (int i = N; i; i--)
for (int j = 2 * i; j
总时间复杂度:(O(NlogN))
两方法对比
方法二时间复杂度更低,方法一能适用更多额外限制。
例题
Counting Rhyme
Small GCD
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net