当前位置：首页 > news >正文

Educational Codeforces Round 86 C - Yet Another Counting Problem（规律+前缀和）

news 来源：原创 2024/5/10 11:45:55

传送门

在这里插入图片描述
1.题目大意：给出一段区间 $[l, r]$ 以及两个数 $a, b$ ，问区间内的有多少个数 $x$ 满足 $(x\%a)\%b ! = (x\%b)\%a$

2.首先对 $[0, 100]$ 内的数打表找规律，尽管答案的区间不包含 $0$ ，但是给出 $0$ 能更浅显的看出规律（比如我这种对找规律不太感冒的人），我们不难发现就是一个裸的循环，循环节的长度为 $l c m (a, b)$ （貌似大部分人推的都是 $a * b$ ?但我感觉是 $l c m (a, b)$ 哇，算了反正都对）

3.显然我们对循环的区间预处理前缀和，后面直接利用前缀和的性质查询。然后重点来了（对我这种蒟蒻来说挺麻烦的）我们究竟是以 $[0, l c m)$ 作为循环区间还是使用 $[1, l c m]$ 作为循环区间呢？我一眼认定 $[0, l c m)$ 是正确的，便去写了，写了之后发现不对，测试了一下当 $a, b$ 是倍数关系时，果然出大错，原来当 $n\%lcm==0$ 时，前缀数组的下标 $0$ 是被当做 $1$ 来使用的，就出现了错误

4.想了想，假设一段数为111000111000111000…，循环节是 $6$ ，从第一个数开始显而易见，但是从第二个数开始数，每6个循环依然是正确的！那么我们处理 $[1, l c m]$ 的正确性就可以保证了

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

void print(int a,int b){ //打表代码
    int res[105];
    for(int i=0;i<=100;i++){
        int x=(i%a)%b,y=(i%b)%a;
        if(x==y) res[i]=1;
        else res[i]=0;
    }
    for(int i=0;i<=100;i++){
        int j=i,cnt=1;
        while(res[j]==res[j+1] && j<=100){
            j++;
            cnt++;
        }
        cout<<res[j]<<" "<<cnt<<endl;
        i=j;
    }
}

ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

int sum[maxn];

ll f(ll x,ll n){
    return x/n*sum[n]+sum[x%n];
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll t,a,b,q;
    //print(4,6);
    cin>>t;
    while(t--){
        cin>>a>>b>>q;
        ll l,r,n=lcm(a,b);
        for(int i=1;i<=n;i++){
            ll x=(i%a)%b,y=(i%b)%a;
            sum[i]=sum[i-1]+(x!=y);
        }
        while(q--){
            cin>>l>>r;
            cout<<f(r,n)-f(l-1,n)<<endl;
        }
        cout<<endl;
    }
    return 0;
}