首页 > 代码库 > 求a，b在区间上的公倍数个数

求a，b在区间上的公倍数个数

2024-08-06 09:17:45   217人阅读

　

　　给你两个数 a，b。问你区间 [1，N]中都是有多少个数是a，b的公倍数。当数据很大的时候，遍历肯定会超时。其实，我们可以首先求出 lcm(a,b)。因为我们知道(a,b)公倍数都是它最小公倍数的倍数。所以，我们只需要求[1,N]中lcm(a,b)的倍数------即在[1,N]中有多少个数能被lcm(a,b)整数。答案就是: N/lcm(a,b)。

　　为不失一般性，我们把区间推广到[N,M]。那么我们显然是可以求[1,N]的值和[1,M]的值。然后减去重叠部分即可。

 

例子：

http://222.197.91.48/acmhome/problemdetail.do?&method=showdetail&id=1643

 

 1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4  5 __int64 GCD(__int64 a, __int64 b) 6 { 7     if(b==0) 8         return a; 9     else return GCD(b, a%b);10 }11 12 int main()13 {14     __int64 n, a, b;15     while(~scanf("%I64d%I64d%I64d",&n, &a, &b))16     {17         __int64 len=a/GCD(a, b)*b;18         printf("%I64d\n",n/len);19     }20     return 0;21 }

 

求a，b在区间上的公倍数个数


联系
我们