193 条题解
-
53g93zhmq (3g93zhmq) LV 8 @ 2019-05-27 12:09:17
#include<iostream> #include<cmath> using namespace std; int m,n,ans; int gcd(int x,int y) { if(y==0) {return x;} return gcd(y,x%y); } int main() { cin>>n>>m; for(int i=1;i<=sqrt(m*n);i++) { if((n*m)%i==0&&gcd(i,(n*m)/i)==n) ans++; } cout<<ans*2; return 0; }
-
22019-09-24 13:25:47@
大概不是最优解...
思路:y/x必为两个互质的数,问原因自己翻数论书去#include <iostream> #include <math.h> using namespace std; int gcd(long a,long b){ return b==0?a:gcd(b,a%b); } int main() { long x,y; cin>>x; cin>>y; long num=y/x; long hits=0; if(y%x!=0){ cout<<0; return 0; } for(long i=1;i<=num;i++){ if(num%i!=0)continue; if(gcd(i,num/i)!=1)continue; ++hits; } cout<<hits; }
-
12018-08-12 10:24:21@
这是一道较为简单的数论题
首先我们拿到这个题可以写个暴力找一下规律,我们会发现答案要么是0要么是2的幂次方,这个时候我们可以想办法去找这个幂次方下面开始正题
根据唯一分解定理可知,任何一个数的分解质因数都只有一种方法
同时,关于LCM和GCD的性质,我们可以得知,对于某个素因子ai,其在GCD中出现的次数等于在x,y中出现次数较少的,在LCM中出现的次数等于在x,y中出现次数较多的
这样的话我们的分解方法就已经固定了,每出现一个素因子bi,假如它在x,y中出现的次数不相同,答案就要乘上2,同时,如果分解过程中GCD的某个素因子数大于LCM中的素因子数,说明答案不存在,此时输出0
数据较小,没有必要筛素数,硬做即可#include<iostream> using namespace std; int p1[1000010],p2[1000010]; int main() { int x,y,i,j,num=0,ans=1,x1,y1; cin>>x>>y; x1=x; y1=y; if(x>y) { cout<<0; return 0; } for(i=2;i<=x;i++) { if(x%i==0) { p1[i]++; x/=i; i--; } } for(i=2;i<=y;i++) { if(y%i==0) { p2[i]++; y/=i; i--; } } for(i=2;i<=y1;i++) { if(p1[i]!=p2[i]) ans*=2; if(p1[i]>p2[i]) { ans=0; break; } } cout<<ans; return 0; }
-
12018-07-13 16:38:44@
本质是分解质因数,求得质因数的数量n(相同的公因数只算1次),最后结果为2^n
PS:前面也考虑过先打个素数表来加快求质因数的数量,然后感觉数据太弱了,而且是一组一个测试,感觉打素数表的代价略大,因此没有实现。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; const int max_n = 1000000; int arr[max_n + 2]; int main() { //freopen("input.txt", "r", stdin); int i, j; // memset(arr, 0, sizeof(arr)); // for(i = 2; i <= sqrt(max_n); ++i) // { // if(!arr[i]) // { // j = i + i; // while(j <= max_n) // { // arr[j] = 1; // j += i; // } // } // } // for(i = 2; i <= max_n; ++i) // { // if(!arr[i]) printf("%d ", i); // } int x0, y0; scanf("%d%d", &x0, &y0); if(y0 % x0 != 0) { printf("0\n"); } else { y0 /= x0; //求质因子 int count = 0; while(y0 != 1) { for(i = 2; i <= y0; ++i) { if(y0 % i == 0) break; } if(arr[count - 1] != i) arr[count++] = i; y0 = y0 / i; } //for(i = 0; i < count; ++i) printf("%d ", arr[i]); printf("%.0lf\n", pow(2, count)); } //fclose(stdin); return 0; }
-
12018-02-11 18:23:09@
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}
int main(){
int a,b,ans=0;
cin>>a>>b;
for(int i=a;i<=b;i+=a){
for(int j=a;j<=b;j+=a)
if(gcd(i,j)==a&&(i/a)*(j/a)*a==b)ans++;
}
cout<<ans;
return 0;
}
-
12017-10-21 20:31:57@
#include<bits/stdc++.h>
using namespace std;
int a,b,ans;
int gcd(int aa,int bb)
{
return bb==0?aa:gcd(bb,aa%bb);
}
int main()
{
cin>>a>>b;
int t=a*b;
for(int i=2;i<=sqrt(t);i++)
if(t%i==0&&gcd(t/i,i)==a) ans++;
cout<<ans*2<<endl;
return 0;
} -
12017-04-19 13:16:23@
还是比较简单的。
思路:枚举两个数,当然从 x 开始。
#include <iostream> using namespace std; int gcd(int m, int n) { return n == 0 ? m : gcd(n, m % n); } int lcm(int m, int n) { return m * n / gcd(m, n); } int main() { int x, y; cin >> x >> y; int _count = 0; for (int i = x; i <= y; i += x) for (int j = x; j <= y; j += x) if (gcd(i, j) == x && lcm(i, j) == y) _count++; cout << _count << endl; return 0; }
-
02023-05-14 21:15:06@
#include<iostream>
#include<cmath>
using namespace std;
int show(int x0,int y0)
{
return x0%y0==0?y0:show(y0,x0%y0);
}
int main()
{
int x0,y0,P,Q,n,count=0;
cin>>x0>>y0;
if(y0%x0!=0)
{
cout<<0<<endl;
return 0;
}
else
{
n=y0/x0;
for(P=1;P<=floor(sqrt(n));P++)
{
if(n%P==0)
{
Q=n/P;
if(show(Q,P)==1)
{
count+=2;
}
}
}
}cout<<count<<endl;
return 0;
} -
02022-08-16 10:42:20@
两个数的最大公因数和最小公倍数的乘积等于这两个数的乘积
#include<bits/stdc++.h> using namespace std; int main() { int x,y; scanf("%d %d",&x,&y); int sum=x*y; int ans=0; for(int i=1;i<=sum;i++) { if(sum%i!=0) continue; int j=sum/i; if(__gcd(i,j)==x) { ans++; } } printf("%d",ans); return 0; }
-
02021-10-08 13:04:33@
#include<iostream>
using namespace std;
int x,y;
int sum;
int a;
int ans;
int gcd(int a,int b)
{
return a%b==0?b:gcd(b,a%b);
}
int main()
{
cin>>x>>y;
sum=y*x;
for(int i=1;i<=y/x;++i)
{
a=i*x;
if(sum%a==0&&gcd(a,sum/a)==x) ++ans;
}
cout<<ans;
} -
02020-04-08 18:03:00@
#include <iostream> #include <algorithm> using namespace std; int GetN(int a, int b) { int t; while (b) { t = a % b; a = b; b = t; } return a; } int main() { int x, y, ans = 0; cin >> x >> y; int s = x * y; for (int i = x; i <= y; i += x) for (int j = i; j <= y; j += x) if(i * j == s && GetN(i, j) == x) { ans++; if(i != j) ans++; } cout << ans << endl; return 0; }
-
02019-07-30 15:52:11@
#include<iostream>
#include<algorithm>
using namespace std;int gcf(int a,int b){
return a*b/__gcd(a,b);
}int main(){
int x,y;
cin>>x>>y;int num=0;
for(int j=x;j<=y;j+=x){
for(int i=x;i<=y;i+=x)
if(__gcd(i,j)==x && gcf(i,j)==y)
num++;
}
cout<<num<<endl;
return 0;
} -
02018-08-27 21:46:14@
#include<cstdio>
using namespace std;
int gys(int a,int b){
int m;
do{
m=a%b;
a=b;
b=m;
}while(m!=0);
return a;
}
int gbs(int c,int d){
int w=gys(c,d);
return c*d/w;
}
int main(){
int x,y,count=0;
scanf("%d %d",&x,&y);
for(int i=x;i<=y;i++){
for(int j=i;j<=y;j++){
if(gys(i,j)==x&&gbs(i,j)==y)
count++;
}
}
printf("%d",count*2);
return 0;
} -
02018-08-08 15:36:24@
兄弟们,我回来了,刚刚拿了把三杀!
var i,j,k,gcd,gbs,t,tot,zs:longint;
begin
readln(gcd,gbs);
if gbs mod gcd<>0 then
begin
writeln('0');halt
end;
t:=gbs div gcd;
i:=1;
while t>1 do
begin
inc(i);
if t mod i=0 then
begin
inc(tot);
while t mod i=0 do t:=t div i;
end;
end;
zs:=trunc(exp(ln(2)*tot));
writeln(zs);
end.
本来有一个超时后来改了一下,这是修改版 -
02018-04-26 15:07:05@
看到你们的题解千篇一律,代码基本一样,我就笑笑。
其实这是一个数学题目,枚举什么的不是因为数据量小,否则要呵呵。
如果最大公约数是a,最小公倍数是b,如果b不能被a整除,那说明不可能有存在答案,所以结果是0。
否则设C = B/A,将C质因数分解,得到的不同质数的个数D,例如C=12,那D=2(2个2,1个3),那D个质数将要么给a,要么给b,因此结果就是2^D,ps:同一个质数不能各分一边,否则最大公约数将不再是b。 -
02018-01-27 14:53:44@
#include <cstdio> using namespace std; int x, y, cnt; int gcd(int m, int n){return n == 0 ? m : gcd(n, m % n);} inline int lcm(int m, int n){return m * n / gcd(m, n);} int main(){ scanf("%d %d", &x, &y); for (int i = x; i <= y; i += x){ for (int j = x; j <= y; j += x){ if (gcd(i, j) == x && lcm(i, j) == y) cnt++; } } printf("%d\n", cnt); return 0; }
-
02017-12-13 14:12:01@
#include<iostream>
#include<cmath>
using namespace std;
int m,n,ans;
int gcd(int x,int y)
{
if(y==0) {return x;}
return gcd(y,x%y);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=sqrt(m*n);i++)
{
if((n*m)%i==0&&gcd(i,(n*m)/i)==n) ans++;
}
cout<<ans*2;
return 0;
} -
02017-11-01 16:36:45@
#include<iostream>
#include<cstdio>
using namespace std;
int a(int m,int n){//最大公约数
if(m<n) swap(m,n);
for(int i=n;i>=1;i--){
if(m%i==0 && n%i==0) {
return i;
}
}
}
int b(int m,int n){//最小公倍数
return m*n/a(m,n);
}
int main() {
int x,y;
cin>>x>>y;
int count=0;
for(int i=x;i<=y;i+=x)
for(int j=x;j<=y;j+=x)
if(a(i,j)==x && b(i,j)==y)
count++;
cout<<count;
return 0;
} -
02017-11-01 16:36:09@
#include<iostream>
#include<cstdio>
using namespace std;
int a(int m,int n){
if(m<n) swap(m,n);
for(int i=n;i>=1;i--){
if(m%i==0 && n%i==0) {
return i;
}
}
}
int b(int m,int n){
return m*n/a(m,n);
}
int main() {
int x,y;
cin>>x>>y;
int count=0;
for(int i=x;i<=y;i+=x)
for(int j=x;j<=y;j+=x)
if(a(i,j)==x && b(i,j)==y)
count++;
cout<<count;
return 0;
} -
02015-02-02 19:07:55@
#include <iostream>
using namespace std;
int yue[10001];
int gcd(int m, int n);
int lcm(int m, int n);
int main()
{
int x, y, cnt = 0, dex = 0;
cin >> x >> y;
for (int i = 2; i <= y; i++)
{
if (y % i == 0)
{
yue[dex++] = i;
}
}
for (int i = 0; i < dex; i++)
for (int j = 0; j < dex; j++)
if (gcd(yue[i], yue[j]) == x && lcm(yue[i], yue[j]) == y)
cnt++;
cout << cnt << endl;
}int gcd(int m, int n)//最大公约数,更相减损法
{
while (m != n)
{
if (m>n) m -= n;
else n -= m;
}
return m;
}
int lcm(int m, int n)//最小公倍数
{
int i;
for (i = (m>n ? m : n);; i++)
if (i%m == 0 && i%n == 0)
return i;
}
简单的搜索,但是不能直接在范围内搜索,那样太费事,这里用点数学方法选出一些数。
如果两个数的最小公倍数是y,那么这两个数是y的约数。
将y的约数筛选出来,再搜索即可