SP11391 EASYMATH - EASY MATH 题解

· · 题解

这题很好得结合了数论和组合的知识，有点 AtCoder 的风格。

首先我们来分析题目。如果使用枚举算法必定会超时；所以我们需要使用数论的方法。

我们先定义一个函数 f(l,r,x)，表示在区间 [l,r] 中能被 x 整除的整数个数。设 l_0=\left\lceil\dfrac{l}{x}\right\rceil,r_0=\left\lfloor\dfrac{r}{x}\right\rfloor，易得 f(l,r,x)=r_0-l_0+1。

接下来是本题的重点。我们先来看本问题的简化版：

求区间 [l,r] 间既不能被 a 整除又不能被 b 整除的整数有多少个。

我们先考虑能被 a 或 b 整除的整数个数，设集合 A=\{x\mid l\le x\le r,a|x\}，集合 B=\{x\mid l\le x\le r,b|x\}。

很显然结果不是 |A|+|B|，因为 A 与 B 有交集。易得交集就是在 [l,r] 区间中既能被 a 整除又能被 b 整除的整数构成的集合，即 A\cap B=\{x\mid l\le x\le r,\operatorname{lcm}(a,b)|x\}（注：这里的 \operatorname{lcm}(a,b) 指 a 与 b 的最小公倍数）。能被 a 或 b 整除且在区间 [l,r] 中的整数共有 |A|+|B|-|A\cap B| 个。

所以，最终答案是 (r-l+1)-(|A|+|B|-|A\cap B|)。

有没有觉得上面的公式很熟悉？

没错，它就是大名鼎鼎的容斥原理。

根据容斥原理，我们就可以得出本题对于 n 个数的通解。

直接上结论吧：

设 A_i 为 [l,r] 区间中能被 a_i 整除的整数集合（|A_i|=f(l,r,a_i)），那么最终 [l,r] 中都不能被 a_1,a_2,...,a_n 整除的整数个数为：

r-l+1-\left(\sum\limits_{i=1}^n{|A_i|}-\sum\limits_{i,j:i\ne j}{|A_i\cap A_j|}+\sum\limits_{i,j,k:i\ne j\ne k}{|A_i\cap A_j\cap A_k|}-\cdots+|A_1\cap A_2\cap \cdots\cap A_n|\right)

本题中 n=5，数据较小，用循环嵌套即可实现。

放代码：

#include<bits/stdc++.h>
#define int long long // 记得开 long long
using namespace std;
int lcm(int n,vector<int> a){
  int s=1;
  for(int i=0;i<n;i++)
    s=s/gcd(a[i],s)*a[i];
  return s;
} // 求 lcm 的过程，可使用 C++17 的 gcd() 函数
int f(int l,int r,int x){
  int l2=l%x?l/x+1:l/x,r2=r/x;
  return r2-l2+1;
} // 上文所述的 f(l,r,x) 函数
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,m,a[5],d,c=0; cin>>n>>m>>a[0]>>d;
    for(int i=1;i<5;i++)a[i]=a[i-1]+d;
    for(int i=0;i<5;i++)c+=f(n,m,a[i]); // 考虑能被单个整数整除的整数个数
    for(int i=0;i<4;i++)
      for(int j=i+1;j<5;j++)
        c-=f(n,m,lcm(2,{a[i],a[j]})); // 考虑能被 2 个整数同时整除的整数个数，下同
    for(int i=0;i<3;i++)
      for(int j=i+1;j<4;j++)
        for(int k=j+1;k<5;k++)
          c+=f(n,m,lcm(3,{a[i],a[j],a[k]}));
    for(int i=0;i<2;i++)
      for(int j=i+1;j<3;j++)
        for(int k=j+1;k<4;k++)
          for(int l=k+1;l<5;l++)
            c-=f(n,m,lcm(4,{a[i],a[j],a[k],a[l]}));
    cout<<(m-n+1)-c-f(n,m,lcm(5,{a[0],a[1],a[2],a[3],a[4]}))<<endl; // 答案输出
  } // 本题为多测
  return 0;
}