校赛Round2 1004 草爷要的数

今天校队队员们准备放松一下，我们队就准备选一些数字玩，然而每个人喜欢的数字是不同的，刻盘喜欢x（1<=x<=1^9），凯凯喜欢y（1<=y<=1^9），而我则喜欢z（1<=z<=1^9），争论不出结果的情况下，我们决定只要是这三个数中任意一个数的倍数我们都取，为了满足游戏要求，我们还决定只要[a,b]范围内的数（1<=a<=b<=1^18），请问满足要求的数一共有多少呢？

注：求a和b的最大公因数函数：
long long gcd(long long a,long long b){
  return b?gcd(b,a%b):a;
}

多组数据（<=1000），请读到文件结尾。
每组数据一行5个整数，x，y，z，a，b，含义及数据范围如题目描述。
注意使用 long long

对于每组数据输出一个整数，表示满足要求的数的个数，每个结果占一行。

2 3 5 1 10
4 6 9 5 20
4 4 8 10 20

8
7
3

分析：

对于闭区间[0,a]范围内，所有m的倍数的数字个数可用a/m计算。

那么x在区间[a,b]内的倍数的个数即为：b/x-(a-1)/x。y，z同理。

需要减去重复计数的数字。这里(x,y),(y,z),(z,x)的公倍数分别多记了一次，还需要加上（x，y，z）的公倍数出现的次数。

会写GCD和LCMP函数就能过，况且题目还给了GCD~。

#include <stdio.h>
long long gcd(long long n,long long m)
{long long t;while (m){t = n%m;n = m;m = t;}return n;
}
long long lcmp(long long n, long long m)
{long long p = gcd(n, m);return (n/p*m);//这里第一次写成了n*m/p，数据溢出WA了，o(╯□╰)o
}
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);long long x, y, z, a, b, lc1, lc2, lc3, lc, ans1, ans2, ans3, ans;while (~scanf("%I64d%I64d%I64d%I64d%I64d", &x, &y, &z, &a, &b)){lc1 = lcmp(x, y);lc2 = lcmp(y, z);lc3 = lcmp(z, x);lc = lcmp(lc1, lc2);//printf("%I64d %I64d %I64d %I64d ", lc1, lc2, lc3, lc);ans1 = (b / x - (a - 1) / x) + (b / y - (a - 1) / y) + (b / z - (a - 1) / z);ans2 = (b / lc1 - (a - 1) / lc1) + (b / lc2 - (a - 1) / lc2) + (b / lc3 - (a - 1) / lc3);ans3 = (b / lc - (a - 1) / lc);ans = ans1 - ans2 + ans3;//printf("%I64d %I64d %I64d ", ans1, ans2, ans3);printf("%I64d\n", ans);}return 0;
}