C. Yet Another Counting Problem

Yet Another Counting Problem

题意很简单，求l到r之间有多少个数x满足 (x%a)%x!=(x%b)%a
a和b的范围很小，很容易想到从a、b下手。
考虑一下如果x=lcm(a,b) 那么一定满足
(x%a)%x==(x%b)%a
结果肯定是以周期性呈现出来的其实每lcm(a,b)个就是一个周期
所以对于每组数据，预处理出来他一个周期内的答案，对于l到r之间
可以计算出[1,r]-[1,l-1]即可
那么每部分只要计算有多少个周期，再乘上一个周期内的答案加上最后多余的部分即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int sum[40005];
int a,b;
ll cal(ll l){
    int lcm=a/__gcd(a,b)*b;
    return l/lcm*sum[lcm]+sum[l%lcm];
}
int main(){
    int t;cin>>t;
    while(t--){
        int q;cin>>a>>b>>q;
        int lcm=a/__gcd(a,b)*b;
        for(int i=1;i<=lcm;i++){
            sum[i]=sum[i-1];
            if(i%a%b!=i%b%a) sum[i]++;
        }
        while(q--){
            ll l,r;
            cin>>l>>r;
            cout<<cal(r)-cal(l-1)<<" ";
        }
        cout<<endl;

    }
    return 0;
}