Yet Another Counting Problem

思路:假设a  <=  b。

x % a % b = x % a是显然成立的,那么只需要比较  x % a !=  x % b % a的情况就可。

通过手写 x % a 和 x % b % a的情况,发现我们只需要写出一个lcm(a,b)的表格(lcm最小公倍数),就是一个循环表,有了循环表,我们只需要统计一个循环表中每个位置不同余数的个数就可以,我们就可以处理1e18的数据了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <functional>
 5 #include <set>
 6 #include <vector>
 7 #include <queue>
 8 #include <cstring>
 9  
10  
11 using namespace std;
12  
13 #define ll long long
14 #define pb push_back
15 #define fi first
16 #define se second
17  
18 const int N = 1010;
19 const int INF = 1e9;
20  
21 int gcd(int a, int b){
22     return b == 0 ? a : gcd(b, a % b);
23 }
24  
25  
26 void solve(){
27     int T;
28     cin >> T;
29     while(T--){
30         int a, b, q;
31         cin >> a >> b >> q;
32         if(a > b) swap(a, b);
33         int lcm = b / gcd(a, b) * a;
34         //cout << "ok" << endl;
35         vector<int > same(lcm + 1);
36         for(int i = 1; i <= lcm; ++i){
37             same[i] = same[i - 1] + ((i % a) != (i % b % a));
38         }
39         ll l, r;
40         while(q--){
41             cin >> l >> r;
42             //cout << l << " " << r << endl;
43             ll ans1 = (ll)same[lcm] * (r / lcm) + same[r % lcm];
44             ll ans2 = (ll)same[lcm] * ((l - 1) / lcm) + same[(l - 1) % lcm];
45             //cout << "ans = ";
46             cout << ans1 - ans2 << " ";
47         }
48         cout << endl;
49     }
50 }
51  
52 int main(){
53     
54     ios::sync_with_stdio(false);
55     cin.tie(0);
56     cout.tie(0);
57     solve();
58     
59     return 0;
60 }

 

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/SSummerZzz/p/12788152.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!