C. Yet Another Counting Problem

Quiz

https://codeforces.com/contest/1342/problem/C

解説

• l～rの範囲で数えたい。0～xまでの範囲で数えることが f(x)でできるなら、f(r) - f(l-1)で求められる。よくあるテク
• 周期a x bで同じ結果となるので、f(0) ～ f(a x b)までを事前計算しておき、fを累積和したものも持っておけば、各クエリO(1)で返せる

AC code

https://codeforces.com/contest/1342/submission/78185813

ll a,b,q;
 
ll T[40010];
 
// 0からrで一致しない数
ll f(ll r){
  if(r==0) return 0;
 
  ll L = a*b;
  ll loop = r/L;
  r %= L;
 
  ll ans = loop * T[a*b];
  ans += T[r];
 
  return ans;
}
 
void solve(){
  cin>>a>>b>>q;

  if(a>b) swap(a,b);
  // a<=bを仮定
 
  rep(i,40010) T[i]=0; // reset
 
  // make table
  rep(i,a*b){
    if(i%a%b != i%b%a) T[i]=1;
  }
  rep(i,a*b){
    T[i+1] += T[i];
  }
 
  VI Ans;
  while(q--){
    ll l,r;cin>>l>>r; 
    ll ans = f(r) - f(l-1);
    Ans.push_back(ans);
  }
  print_vector(Ans);
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N; 
    cin>>N;
    
    while(N--){
      solve();
    }
    
    return 0;
}