[51Nod 1222] - 最小公倍数计数 (..怎么说 枚举题?)

题面

题目分析

令
则

此处表示小于等于中,满足两个数互质且乘积为的无序数对的个数,显然
其中表示d的质因子个数

相当于把d的质因数分成两部分,所以就每个质因数选或不选,又因为是无序数对,所以除以2,也可以写为以下形式

• 有没有发现十分类似某个等式,记与互质的数的和为(随便选的字母),则
• 

回到这道题,有
然后我们又发现其实是每个质因数选或不选的方案数,及的无平方因子的约数的个数,所以根据函数的定义,我们知道只有无平方因子数的函数值才为1或-1,所以加上绝对值就成了计数

• 先看第二个，对于某一个的取值，把它记作，就以的范围做整除分块优化，的时间复杂度，那么外层还有一个求和，于是在外面也套一层整除分块优化，预处理出前后时间复杂度为

• 此处预处理为线性筛，考虑变换，实际可看作枚举后看以内有多少个数能被整除，这不就是吗？(这个函数表示i的约数个数)
  于是我们只需要筛出约数个数在累加就行了，线性筛时存一下当前数的最小质因子的次数就可以愉快的线性筛了

• 由于在外面一层套上了整除分块优化，则需要求出的前缀和，也就是以内的无平方因子数

• 这里处理无平方因子数时用容斥原理，有
  想想函数的定义，这个容斥还是比较好理解的
  可处理出来

• 其实这道题用的是[SPOJ] DIVCNT2 - Counting Divisors (square)一模一样的方法(我后面的分析都是直接粘的233)
• 但是奈何这道题的卡内存!(各种预处理+卡内存我只能做到6015ms>6000ms T了…)
• 只能想想别的办法(也许有些同学掌握特殊的卡常技巧能过A掉吧)

.
.
.
.
.
好的。

正文开始

那么我就要开始略讲一点了

定义
则

考虑怎么求
设,则
反演一下得到不考虑的话就是三个数的乘积的统计,做法为统计的数对的数量

分别考虑三个数不相等/两个数相等/三个数相等的情况再分别乘上排列系数

由于这样的枚举只需要枚举,在枚举,然后统计的个数

比较讨厌,假设与被统计两次,因为有的情况不能直接除以
回到原问题,当时,由于,所以,此时有种取值,所以只需要在算出的结果加上再除以即可
参考自 ​​​51Nod 题解1楼​​

时间复杂度证明

设表示统计满足的的三元组个数的时间复杂度

上面的是枚举时从开始枚举,总时间复杂度此处的枚举应该是离散的,我们将它看做连续的,由于那么将两两结合,有
于是我们又回到离散的,最多有对这样的关系,所以
所以总时间复杂度为
申明:以上的符号纯属乱用,只是不能再用表示的取值可能不为整数的和了

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 316228;
int Cnt, Prime[N], mu[N];
bool IsnotPrime[N];

void init()
{
  mu[1] = 1;
  for(int i = 2; i < N; ++i)
  {
    if(!IsnotPrime[i])
      Prime[++Cnt] = i, mu[i] = -1;
    for(int j = 1; j <= Cnt && i * Prime[j] < N; ++j)
    {
      IsnotPrime[i * Prime[j]] = 1;
      if(i % Prime[j] == 0) { mu[i * Prime[j]] = 0; break; }
      mu[i * Prime[j]] = -mu[i];
    }
  }
}

LL solve(LL n)
{
  LL ret = n;
  for(int d = 1; (LL)d*d <= n; ++d) if(mu[d])
  {
    LL m = n/((LL)d*d), s = 0;
    for(int a = 1; (LL)a*a*a <= m; ++a)
    {
      for(int b = a+1; (LL)a*b*b <= m; ++b)
        s += (m/((LL)a*b)-b) * 6 + 3; // * 6 -> a < b < c ( P(3,3) = 6 )
                        // + 3 -> a < b = c ( P(3,3)/P(2,2) = 3)
      s += (m/((LL)a*a)-a) * 3 + 1; // * 3 -> a = b < c ( P(3,3)/P(2,2) = 3 )
                      // + 1 -> a = b = c
    }//以上的"-b","-a"都是为了满足 c>b 或 c>b=a,跟时间复杂度的分析一样
    ret += s * mu[d];
  }
  return ret / 2;
}

int main ()
{
  LL a, b; init();
  scanf("%lld%lld", &a, &b);
  printf("%lld\n", solve(b)-solve(a-1));
}

.
.
可写死我了