Codeforces_340A_The Wall(简单题)

118 阅读 0 评论 78 点赞

我是靠谱客的博主老实吐司，这篇文章主要介绍Codeforces_340A_The Wall(简单题)，现在分享给大家，希望可以做个参考。

题型：（数论）

题意：

两个人涂板砖，从第一块涂起，甲每隔x块涂一个，乙每隔y块涂一个。对于给出的区间[a,b]，问区间内有几块板砖都被他俩涂过。

分析：
只有x和y的最小公倍数的倍数板砖才会被涂上两种颜色，所以就找到a后面的第一个lcm(x,y)的倍数h，然后答案即为：
ans = (b-a)/lcm(x,y) + 1 ,(h<=b)

ans = 0 ,(h>b)

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
int lcm(int a,int b){
return a / gcd(a,b) * b;
}
int main(){
int x,y,a,b;
while(~scanf("%d%d%d%d",&x,&y,&a,&b)){
int d = lcm(x,y);
bool flag = true;
int ans;
while(1){
if(a%d==0){
break;
}
a++;
if(a>b){
flag = false;
break;
}
}
if(!flag){
printf("0n");
}
else{
ans=(b-a)/d;
ans++;
printf("%dn",ans);
}
}
return 0;
}