华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1192|回复: 1
打印 上一主题 下一主题

P1029 最大公约数和最小公倍数问题

[复制链接]

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
跳转到指定楼层
楼主
发表于 2018-11-24 21:17:24 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P1029题目描述
输入22个正整数x_0,y_0(2 \le x_0<100000,2 \le y_0<=1000000)x0​,y0​(2≤x0​<100000,2≤y0​<=1000000),求出满足下列条件的P,QP,Q的个数
条件:
  • P,QP,Q是正整数
  • 要求P,QP,Q以x_0x0​为最大公约数,以y_0y0​为最小公倍数.

试求:满足条件的所有可能的22个正整数的个数.
输入输出格式输入格式:

22个正整数x_0,y_0x0​,y0​

输出格式:

11个数,表示求出满足条件的P,QP,Q的个数

回复

使用道具 举报

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
沙发
 楼主| 发表于 2018-11-24 21:17:45 | 只看该作者
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. using namespace std;
  5. typedef long long ll;
  6. #define FOR(i,a,b)for(register ll i=a;i<=b;++i)
  7. long long s,r1;
  8. ll gcd(ll m,ll n){return n==0?m:gcd(n,m%n);}
  9. int x,y,ans;
  10. int main()
  11. {
  12.     scanf("%d%d",&x,&y);
  13.     if(y%x){cout<<0;return 0;}
  14.     ll zs=y/x;
  15.     ll sqrtt=sqrt(zs);
  16.     FOR(i,1,sqrtt)
  17.     {
  18.         if(zs%i!=0) continue;
  19.         if(gcd(i,zs/i)==1) ans++;
  20.     }
  21.     ans=ans<<1;
  22.     cout<<ans;
  23.     return 0;
  24. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-25 14:08 , Processed in 0.179536 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表