[SPOJ] DIVCNT2 - Counting Divisors (square) (平方的约数个数前缀和 容斥 卡常)

题目

vjudge URL:​​Counting Divisors (square) ​​​ Let be the number of positive divisors of .

For example, , and .

Let

Given , find .

Input

First line contains (), the number of test cases.

Each of the next lines contains a single integer . ()

Output

For each number , output a single line containing .

Example

• Input

5
1
2
3
10
100

• Output

1
4
7
48
1194

• Explanation for Input
  

Information

There are 6 Input files.

• Input #1: , TL = 1s.
• Input #2: , TL = 20s.
• Input #3: , TL = 20s.
• Input #4: , TL = 20s.
• Input #5: , TL = 20s.
• Input #6: , TL = 20s.

My C++ solution runs in 5.3 sec. (total time) //呵呵

Source Limit is 6 KB.*

题目分析

表示的约数个数,即

前言

• mdzz，写了1h的Latex公式没保存。。因为机房电脑的烂CPU，本地测这道题的极限数据时崩溃了c
• 这道题是真的卡常，最后点线性筛必须筛到很大，5e7能过，1e7、2e7都不行(可能因为我是大常数选手吧，悄悄打上卡常的FLAG)
• 本地评测炸电脑，真的无语。。
• 刚开始模了1e9+7 WA了好久。。。
• 由于是求函数前缀和，又和杜教筛的题一起做的，就放在杜教筛/莫比乌斯反演里吧

正文

设
则
将看作是 只由(乘起来)构成的的约数的个数,因为每一个约数都对答案造成了对应的的贡献,那么
其中表示d的质因子的个数(想想)
与此同时，我们又发现实质上是的质因子选或不选的方案数,也就是的无平方因子的约数的个数，则
因为根据函数的定义，只有无平方因子数的函数值才为或，加上绝对值就相当于统计了个数(有的题解也写的是,个人认为第一眼看到这个平方会懵一会)

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

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

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

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

综上，各种操作之后把时间复杂度降到了

等等，真的降到了吗？？！看看降到的条件？

• 预处理出前

然而掀桌)
所以只能尽可能的接近，实测能过，都会TLE

CAUTION

首先做这道题，如果电脑是机房的老电脑/旧电脑/烂电脑，不要像作死去测什么的极限数据，反正我是卡爆了(逃)
也不要像我一样边写代码边写博客，更不要卡住之后作死的乱点一气把浏览器搞炸了，我写了的啊!!!(这里的公式已经是精简版了)
最后一句忠告，写博客多按保存(富文本编辑器似乎会过一会就自动保存一下，不过不能写数学公式)，写代码也是…

AC code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5e7 + 1;//!!!
int Prime[MAXN], mu[MAXN], d[MAXN], Min_a[MAXN], Cnt;
bool IsnotPrime[MAXN];
LL sum_d[MAXN], sum_mu[MAXN];
void init(int n)//线性筛，Min_a[i]存的是i最小质因子的次数
{
  d[1] = mu[1] = 1;
  for(int i = 2; i <= n; ++i)
  {
  
    if(!IsnotPrime[i])
      Prime[++Cnt] = i, mu[i] = -1, d[i] = 2, Min_a[i] = 1;
    for(int j = 1, v; j <= Cnt && i * Prime[j] <= n; ++j)
    {
      v = i * Prime[j];
      IsnotPrime[v] = 1; Min_a[v] = 1;
      if(i % Prime[j] == 0)
      {
        Min_a[v] += Min_a[i];
        mu[v] = 0;
        d[v] = d[i] / Min_a[v] * (Min_a[v] + 1);
        break;
      }
      mu[v] = -mu[i];
      d[v] = d[i]<<1;
    }
  }
  for(int i = 1; i <= n; ++i)
    sum_d[i] = sum_d[i-1] + d[i],
    sum_mu[i] = sum_mu[i-1] + mu[i]*mu[i];
}
inline LL Sum_mu(LL n)//莫比乌斯函数的绝对值的前缀和/[1,n]无平方因子数个数
{
  if(n < MAXN) return sum_mu[n];
  LL ret = 0;
  for(LL i = 1; i*i <= n; ++i)
    ret += mu[i] * (n/(i*i));
  return ret;
}
inline LL Sum_d(LL n) //约数个数前缀和
{
  if(n < MAXN) return sum_d[n];
  LL ret = 0;
  for(LL i = 1, j; i <= n; i=j+1)
  {
    j = n/(n/i);
    ret += (n/i) * (j-i+1);
  }
  return ret;
}

inline LL solve(LL n)
{
  LL ret = 0;
  for(LL i = 1, j; i <= n; i=j+1)
  {
    j = n/(n/i);
    ret += (Sum_mu(j)-Sum_mu(i-1)) * Sum_d(n/i);
  }
  return ret;
}

int main ()
{
  LL T, n;
  scanf("%lld", &T);
  init(T > 800 ? 10000 : MAXN-1); //优化
  while(T--)
  {
    scanf("%lld", &n);
    printf("%lld\n", solve(n));
  }
}

参见 ​​传送门:大佬博客​​ …
…
…
…
…

再次吐槽数学公式的难打