CF1342C Yet Another Counting Problem 题解

无咕_ · 2021-08-10 11:33:22 · 题解

题解索引

1. 题目大意
2. Solution
3. AC code
4. 类似题型

代码类型： C++（cpp）

是否吸氧：否

不压行代码长度：29

这篇题解挺长的，慎点。

题目大意

题面： <传送门>

题意：

初始给出 a,b 给出 q 次询问，每次询问如下：

给出 l,r，求在区间 [l,r] 中，有多少个数 i 满足 (i\bmod a)\bmod b\ne (i\bmod b)\bmod a。

有 T 组询问！

术语理解： 小学数学，周期问题和最小公倍数。

Solution

首先排除暴力，单是一组极限数据 1\le l_i\le r_i \le 10^{18} 就爆了，更别说 1\le q\le 500 和 1\le T\le 100 了。

Part 1 思路引入

我们先来看这个：

这证明，取模的结果是有一定规律的 突然回到扩欧。

比如：

我们把 x\bmod 3=2 中的 x 都列出来：

我们发现，这些数之间是有一定规律的，相邻两个数的差是 3。

可以得出：

我们把原题的式子拿过来嗷：

我们先处理一个：

我们在计算是 a,b 分别会被消去，所以并无大碍。

而我们之前说过，取模的结果是有一定规律的。所以，我们可以得出这玩意：

我们再把另一个式子也进行这样处理（这里不放了，与这个一样，就是把模数换了）。于是，这就成了一个周期问题。

Part 2 周期问题

Q：这啥啊，跟这题有关联吗？

A：没关联我能放上来嘛？ 好像真能

我们再把刚刚求得的公式搬过来：

我们发现，相邻的两个数之间的不同是 1ab 。那么，我们是否可以转化成之前那样的等差数列形式呢？答案是可以的。

如果抛去取模不说，相邻两个数之间的差异确实是 1ab。这样，不就构成了一个循环的周期（因为答案都相同）？

如果我们处理第二组中的数时，是否可以看出处理第一组中的数呢？答案是可以的。

举个取模的例子，比如 \bmod 3

可以轻松得出一个周期是：

那我们求任何一个周期中的某数时，是不是也可以从这个周期里找呢？比如我们求 5\bmod 3 ，我们可以知道 5 在第二个周期中（因为 \lceil \frac{5}{3}\rceil = 2），而在第二个中多了 5-3\times \lfloor \frac{5}{3}\rfloor =2 所以我们直接找第二个周期中的第二个就行。可所有周期都一样，我们也可以在第一个周期中找！

这个问题不就轻松解决了？

Part 3 整理思路

之前我们说过了，一个周期就是 1ab 。那我们只需要预处理出第一个周期，剩下的周期都迎刃而解了！

看到这种题很容易想到前缀和吧？既省时又省力。

那怎么求最小公倍数呢？

这里 lcm 就是最小公倍数的意思，至于这个式子的证明……可以去学一下算数基本定理，建议直接 bdfs 。

注意！有一个坑点！最后我们在处理每对 l,r 时，虽然只需要前缀和处理一下就完了，但是要注意前缀和的处理！

因为 l,r 有可能不在同一个周期里，所以我们要将 [1,l-1] 和 [1,r] 都处理出来再相减！具体意思可以看代码里的注释。

AC code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX=40009;
typedef long long ll;
int t,q;
ll s[MAX];
ll a,b;
int gcd(int a,int b){//获取最大公因数
    return b==0?a:gcd(b,a%b);
}int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld %d",&a,&b,&q);
        ll _lcmab=a*b/gcd(a,b);//前面说过这个方法
        for(int i=1;i<=_lcmab;i++){//注意是处理到lcm(a,b)
            s[i]=s[i-1];//首先赋值过来
            if(i%a%b!=i%b%a)s[i]++;//如果符合要求就+1
        }for(int i=1;i<=q;i++){
            ll l,r;
            scanf("%lld %lld",&l,&r);
            //前面说过，要求出1到l-1和1到r的值后再相减，因为l和r可能不在一个区间中
            ll rx=(r/_lcmab)/*周期数*/*s[_lcmab]/*完整周期的计算*/+s[r%_lcmab/*剩下的数量*/]/*剩下的值（构不成周期的）*/;
            ll lx=((l-1)/_lcmab/*周期数*/)*s[_lcmab]/*完整周期计算*/+s[(l-1)%_lcmab/*剩下的数量*/]/*剩下的值*/;
            printf("%lld ",rx-lx);//输出跟空格即可
        }
    }
    return 0;
}

AC 记录 <传送门>

类似题目

此题考查了最小公倍数和最大公约数的求法，最简单的例题：

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题