Nastya Studies Informatics CodeForces - 992B (大整数)
1 second
256 megabytes
standard input
standard output
Today on Informatics class Nastya learned about GCD and LCM (see links below). Nastya is very intelligent, so she solved all the tasks momentarily and now suggests you to solve one of them as well.
We define a pair of integers (a, b) good, if GCD(a, b) = x and LCM(a, b) = y, where GCD(a, b) denotes the greatest common divisorof a and b, and LCM(a, b) denotes the least common multiple of a and b.
You are given two integers x and y. You are to find the number of good pairs of integers (a, b) such that l ≤ a, b ≤ r. Note that pairs (a, b) and (b, a) are considered different if a ≠ b.
The only line contains four integers l, r, x, y (1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ y ≤ 109).
In the only line print the only integer — the answer for the problem.
1 2 1 2
2
1 12 1 12
4
50 100 3 30
0
In the first example there are two suitable good pairs of integers (a, b): (1, 2) and (2, 1).
In the second example there are four suitable good pairs of integers (a, b): (1, 12), (12, 1), (3, 4) and (4, 3).
In the third example there are good pairs of integers, for example, (3, 30), but none of them fits the condition l ≤ a, b ≤ r.
题意:在一个区间里找有序对数,使得最大公约数和最小公倍数为题目所给
题解:大数 爆搜会超时,先化个简
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=; int gcd(int a,int b)
{
if(b==)
return a;
return gcd(b,a%b);
}
int main()
{
int l,r,x,y,i,num,ans=;
cin>>l>>r>>x>>y;
num=y/x;
if(y%x!=)
{
cout<<""<<endl;
return ; }//num=n*z
for(i=;i*i<=num;i++)
{
int j=num/i;
if(num%i==&&gcd(i,j)==&&l<=i*x&&i*x<=r&&l<=j*x&&j*x<=r)
{
if(i==j)
ans=ans+;
else
ans=ans+;
}
}
cout<<ans<<endl;
}
最新文章
- 如何写一个HttpClient[1]——URI的处理
- Android中ActionBar的使用
- JAVA6开发WebService (三)——几个概念
- Mysql学习笔记(十)存储过程与函数 + 知识点补充(having与where的区别)
- check the element in the array occurs more than half of the array length
- CCF真题之ISBN号码
- EXT经验--查询items的xtype
- python tornado+mongodb的使用
- listview的动态加载数据问题
- SQLite 入门教程(二)创建、修改、删除表
- Spring Data JPA 多个实体类表联合视图查询
- 【问题解决】syntax error: unexpected end of file或-bash: ./full_build.sh: /bin/bash^M: bad interpreter: No
- 优化设计提高sql类数据库的性能
- windows下 gvim8.0 编译器配置
- macOS10.13.2配置TensorFlow
- poj1193 内存分配
- python3 aes加解密
- Microsoft.AspNet.Identity: UserID用整型数据表示, 而不是GUID
- Quartz的基本使用之入门(2.3.0版本)
- UVa 1631 密码锁
热门文章
- keil-rtx
- github新手指南
- 洛谷P3928 SAC E#1 - 一道简单题 Sequence2
- java编程基础二进制
- Date 对象 时间格式注意事项
- servlet config
- selenium报错信息-- Python 中 &#39;unicodeescape&#39; codec can&#39;t decode bytes in position XXX: trun错误解决方案
- [Python] - 使用chardet检查网页编码格式时发现的问题
- jsp另外五大内置对象之-exception
- PHP的优良习惯(转)