题目大意
求出一个正整数 xxx 满足 gcd(x,a0)=a1\tt{gcd(x,a_0)=a_1}gcd(x,a0 )=a1 且 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 。
解题思路
首先想到的是直接枚举 xxx，如果满足要求则累加答案，因为 x>b1x>b_1x>b1 一定不满足 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 ，所以 xxx 从 111 一直枚举到 b1b1b1。代码如下：
时间复杂度 O(n⋅b1)O(n\cdot b_1)O(n⋅b1 )，只适用于 50%50\%50% 的数据，需要再优化。
优化思路
因为 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 的前提条件是 x∣b1x\mid b_1x∣b1 ，即 xxx 是 b1b_1b1 的因数，枚举 b1b_1b1 的因数的时间复杂度是 O(b1)O(\sqrt{b_1})O(b1 )，再判断是否满足 gcd(x,a0)=a1\tt{gcd(x,a_0)=a_1}gcd(x,a0 )=a1 和 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 的条件即可，时间复杂度 O(n⋅b1)O(n\cdot\sqrt{b_1})O(n⋅b1 )。
参考代码
