NC673 题解 | #整除问题#

题意分析

• 给定 $a,b,c,da,\; b,\; c,\; d$a,b,c,d，求所有 $x\times yx\; \backslash times\; y$x×y 被 2021 整除的$(x,y)(x,\; y)$(x,y) 数对个数，其中 $a\le x\le b,c\le y\le da\le x\le b,c\le y\le d$a≤x≤b,c≤y≤d。

思路分析

• 首先，我们进行分析，我们发现，2021=1x2021=43x47,所以我们可以利用容斥进行处理。然后，我们需要了解的一个知识点是一个前缀和的思想。在一个区间[a,b]内的数字x的倍数是$b/x-(a-1)/xb/x-(a-1)/x$b/x−(a−1)/x.

• 接下来，我们进一步分析如何进行容斥。首先，我们来讨论43和47这一对的情况。2021是由这两个数字组合在一起的情况是（左区间有43的倍数和有区间有47的倍数+左区间有47的倍数和有区间有43的倍数-左右区间都有43的倍数和47的倍数的情况）。然后，我们讨论2021和1的情况，但是，我们发现，其实这种组合的一部分情况在43和47这一组的情况中就计算到了。所以我们2021和1的情况应该就只有一边有2021的倍数另一边没有43的倍数和47的倍数的情况。

• 具体请看相关代码仔细理解

C++版本

• 代码如下
  • 过程中只使用了少数的计算，时间复杂度为$O\left(1\right)O(1)$O(1)
  • 只使用了少数的几个变量进行计算，空间复杂度为$O\left(1\right)O(1)$O(1)

class Solution {
public:
    /**
     * 寻找所有能整除 2021 的数对个数
     * @param a long长整型 
     * @param b long长整型 
     * @param c long长整型 
     * @param d long长整型 
     * @return long长整型
     */
    typedef long long ll;
    // 计算[a,b]区间内c的倍数的个数
    ll deal(ll a,ll b,ll c){
        return b/c-(a-1)/c;
    }
    long long findPairs(long long a, long long b, long long c, long long d) {
        // write code here
        ll ans=0;
        ll x=43,y=47; // 求得两个因数x和y
        ll num1=deal(a,b,x); // 前一个区间范围内因数x的倍数的个数
        ll num2=deal(c,d,x);  // 后一个区间范围内的因数y的倍数的个数
        ll num3=deal(a,b,y);  // 前一个区间范围内的因数x的倍数的个数
        ll num4=deal(c,d,y);  // 后一个区间范围内的因数y的倍数的个数
        ll num5=deal(a,b,2021);  // 前一个区间范围内的两个因数的积的倍数
        ll num6=deal(c,d,2021); // 后一个区间范围内的两个因数的积的倍数
        ans+=num1*num4+num2*num3-num5*num6;
        
        // 1x2021的情况，但是需要其中一边没有43和47的
        // 现在就剩下一边有2021，另一边没有43和47的情况了
        ans+=deal(a,b,2021)*(deal(c,d,1)-deal(c,d,43)-deal(c,d,47)+deal(c,d,2021));
        ans+=deal(c,d,2021)*(deal(a,b,1)-deal(a,b,43)-deal(a,b,47)+deal(a,b,2021));
        return ans;
    }
};

Go版本

• 代码如下
  • 过程中只使用了少数的计算，时间复杂度为$O\left(1\right)O(1)$O(1)
  • 只使用了少数的几个变量进行计算，空间复杂度为$O\left(1\right)O(1)$O(1)

package main

/**
 * 寻找所有能整除 2021 的数对个数
 * @param a long长整型 
 * @param b long长整型 
 * @param c long长整型 
 * @param d long长整型 
 * @return long长整型
*/

func deal(a, b, c int64) int64 {
    return b/c-(a-1)/c;
}
func findPairs( a int64 ,  b int64 ,  c int64 ,  d int64 ) int64 {
    // write code here
    var ans int64
    ans = 0
    // 利用容斥求出43x47的情况
    ans += deal(a,b,43)*deal(c,d,47);
    ans += deal(c,d,43)*deal(a,b,47);
    ans -=deal(a,b,2021)*deal(c,d,2021);
    
    // 继续求出1x2021的情况，注意只能一边有2021的倍数另一边没有43和47的倍数
    ans+=deal(a,b,2021)*(deal(c,d,1)-deal(c,d,43)-deal(c,d,47)+deal(c,d,2021));
    ans+=deal(c,d,2021)*(deal(a,b,1)-deal(a,b,43)-deal(a,b,47)+deal(a,b,2021));
    
    return ans;
}