[bzoj 2693] jzptab & [bzoj 2154] Crash的数字表格 (莫比乌斯反演)

题目描述

组数据,给出,,求

题目分析

直接开始变换,假设N<M

总算推完了…
此时只需要线性筛出,然后处理的前缀和
而可以出
利用整除分块优化,时间复杂度为

AC code([bzoj 2693] jzptab)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 10000005, mod = 1e8+9;
int N, M;
namespace Mobius
{
  int mu[MAXN], Prime[MAXN], cnt;
  bool IsnotPrime[MAXN];
  int sum[MAXN];
  void init()
  {
    sum[1] = 1;
    for(int i = 2; i <= MAXN-5; i++)
    {
      if(!IsnotPrime[i]) Prime[++cnt] = i, sum[i] = 1-i;
      for(int j = 1; j <= cnt && i * Prime[j] <= MAXN-5; j++)
      {
        IsnotPrime[i * Prime[j]] = 1;
        if(i % Prime[j] == 0) { sum[i * Prime[j]] = sum[i]; break; }
        sum[i * Prime[j]] = 1ll * sum[i] * (1 - Prime[j]) % mod;
      }
    }
    for(int i = 1; i <= MAXN-5; i++)//前缀和
      sum[i] = (sum[i-1] + 1ll*sum[i]*i%mod) % mod;
  }
  int Sum(int N, int M)
  {
    return ((1ll*N*(N+1)/2) % mod) * ((1ll*M*(M+1)/2) % mod) % mod;
  }
  int calc(int N, int M)
  {
    int ret = 0;
    for(int i = 1, j; i <= N; i=j+1)//整除分块
    {
      j = min(N/(N/i), M/(M/i));
      ret = (ret + 1ll * (sum[j] - sum[i-1]) % mod * Sum(N/i, M/i) % mod) % mod;
    }
    return ret;
  }
}
using namespace Mobius;
int main ()
{
  int T; init();
  scanf("%d", &T);
  while(T--)
  {
    scanf("%d%d", &N, &M); if(N > M) swap(N, M);
    printf("%d\n", (calc(N, M) + mod) % mod);
  }
}

AC code([bzoj 2154] Crash的数字表格)

这道题有个恶心的地方,不能用来预处理,否则会,要读入,后再处理

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 10000005, mod = 20101009;
int N, M;
namespace Mobius
{
  int mu[MAXN], Prime[MAXN], cnt;
  bool IsnotPrime[MAXN];
  int sum[MAXN];
  void init()
  {
    sum[1] = 1;
    for(int i = 2; i <= N; i++)
    {
      if(!IsnotPrime[i]) Prime[++cnt] = i, sum[i] = 1-i;
      for(int j = 1; j <= cnt && i * Prime[j] <= N; j++)
      {
        IsnotPrime[i * Prime[j]] = 1;
        if(i % Prime[j] == 0) { sum[i * Prime[j]] = sum[i]; break; }
        sum[i * Prime[j]] = 1ll * sum[i] * (1 - Prime[j]) % mod;
      }
    }
    for(int i = 1; i <= N; i++)
      sum[i] = (sum[i-1] + 1ll*sum[i]*i%mod) % mod;
  }
  int Sum(int N, int M)
  {
    return ((1ll*N*(N+1)/2) % mod) * ((1ll*M*(M+1)/2) % mod) % mod;
  }
  int calc(int N, int M)
  {
    int ret = 0;
    for(int i = 1, j; i <= N; i=j+1)
    {
      j = min(N/(N/i), M/(M/i));
      ret = (ret + 1ll * (sum[j] - sum[i-1]) % mod * Sum(N/i, M/i) % mod) % mod;
    }
    return ret;
  }
}
using namespace Mobius;
int main ()
{
  scanf("%d%d", &N, &M); if(N > M) swap(N, M); init();
  printf("%d\n", (calc(N, M) + mod) % mod);
}