Codeforces Round #489 (Div. 2) ---- B. Nastya Studies Informatics
程序员文章站
2022-06-08 15:54:28
...
这题给了我们gcd和lcm,和范围,求在范围内有多少对这样的数满足gcd = x , lcm = y
我们可知这两个数的乘积,如果枚举它的因子非常慢O(1e9) ,因为两个数都是gcd的倍数,那么我们可以分别设他们是gcd 的k1倍,k2倍,因此就有 k1 * x * k2 * x = x * y => k1 * k2 = y / x; 而 y / x 最大 就是 1e9 ,那么 时间复杂度就是 O (sqrt(1e9)) ,暴力枚举k1,就可以求出a*b的所有因子个数,但是并不所有因子都符合条件
1、这些因子要在l 和 r 范围内。 2、 gcd(k1 * x, y/x/k1 * x) == x && lcm (k1*k,y/x/k1*x) == y
记录满足这些条件的因子数
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){if (b == 0) return a; return gcd(b , a%b);}
LL lcm(LL a,LL b){ return a/gcd(a,b)*b;}
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int main(){
LL l,r,x,y,cnt = 0;
cin >> l >> r >> x >> y;
for (int i=1; i<=sqrt(y/x); i++) {
if ((y/x) % i == 0 && gcd(i, (y/x)/i) == 1 && lcm(i*x, (y/x)/i*x) == y){
if (l <= i*x && i*x <= r && l <= (y/x)/i*x && (y/x)/i*x <= r){
if ((y/x)/i == i) cnt += 1;
else cnt += 2;
}
}
}
cout << cnt << endl;
return 0;
}
上一篇: P1616 疯狂的采药(DP,完全背包,洛谷,java)
下一篇: Java用for循环输出菱形
推荐阅读
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #461 (Div. 2) B. Magic Forest(异或的性质)
-
Codeforces Round #663 (Div. 2) B. Fix You
-
Codeforces Round #658 (Div. 2) B. Sequential Nim
-
B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)
-
Codeforces Round #666 (Div. 2)B. Power Sequence(等比数列)
-
Codeforces Round #664 (Div. 2) B. Boboniu Plays Chess
-
Codeforces Round #272 (Div. 2) B. Dreamoon and WiFi (超几何
-
Codeforces Round #258 (Div. 2) B. Sort the Array (模拟)
-
Codeforces Round #657 (Div. 2) B. Dubious Cyrpto(思维,数学)