Educational Codeforces Round 86 (Rated for Div. 2)---C

做法预处理0~a*b；

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define sc(a) scanf("%lld",&a)
#define scc(a,b) scanf("%lld%lld",&a,&b)
#define sccc(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define scccc(a,b,c,d) scanf("%lld%lld%lld%lld",&a,&b,&c,&d)
#define sccccc(a,b,c,d,e) scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e)
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 9901
#define N 500010
map <int,int> ci;
typedef long long ll;
ll t,k,j,n,ans=0,xx,y,maxn=(1ll<<31)-1,l,r,i,sum=0,x,a,b,q;
ll dp[500010];
void ge()
{
    cin>>l>>r;
    x=(l-1)/(a*b);
    x=dp[a*b]*x+dp[(l-1)%(a*b)];
    y=(r)/(a*b);
    y=dp[a*b]*y+dp[(r)%(a*b)];
    cout<<y-x<<' ';
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>t;
    while(t--){
            cin>>a>>b>>q;
    for(i=1;i<=a*b;i++)
    {
        if((i%a)%b==(i%b)%a)
            dp[i]=dp[i-1];
        else
            dp[i]=dp[i-1]+1;
    }
    while(q--)
    ge();
    cout<<'\n';
    }
}