Codeforces ECR86 C. Yet Another Counting Problem(规律,区间)

阅读原文时间：2023年07月08日阅读：3

题意:给你两个正整数a和b,询问q次,每次给你一个区间[l,r],问[l,r]中有多少数字满足:x%a%b!=a%b%a.

题解:看公式无从下手的题,一般都是要找规律的.首先,我们知道,假如_x%a%b!=x%b%a,那么:(x+lcm(a,b))%a%b!=(x+lcm(a,b))%b%a,(这个知识在exgcd中很常用).所以,我们打表发现,这其实是一个循环节的问题._

　　　首先枚举[1,lcm]中有多少不相同的,然后每次询问,我们处理一下区间就好了,公式:(r/lcm-(l-1)/lcm)*num[lcm]+num[r%lcm]-num[(l-1)%lcm]

　代码:

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #define ll long long
14 #define fi first
15 #define se second
16 #define pb push_back
17 #define me memset
18 const int N = 1e6 + 10;
19 const int mod = 1e9 + 7;
20 using namespace std;
21 typedef pair PII;
22 typedef pair PLL;
23
24 int t;
25 ll a,b,q;
26 ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
27 ll l,r;
28 ll num[N];
29 ll lcm;
30
31 int main() {
32 ios::sync_with_stdio(false);
33 cin>>t;
34 while(t--){
35 cin>>a>>b>>q;
36 lcm=a*b/gcd(a,b);
37 for(int i=1;i<=lcm;++i){ 38 num[i]=num[i-1]; 39 if(i%a%b!=i%b%a) num[i]++; 40 } 41 while(q--){ 42 cin>>l>>r;
43 printf("%lld ",(r/lcm-(l-1)/lcm)*num[lcm]+num[r%lcm]-num[(l-1)%lcm]);
44 }
45 puts("");
46 }
47 return 0;
48 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章