hdu 5974 A Simple Math Problem(数学题)
2024-09-01 06:54:51
Problem Description
Given two positive integers a and b,find suitable X and Y to meet the conditions:
X+Y=a
Least Common Multiple (X, Y) =b
Input
Input includes multiple sets of test data.Each test data occupies one line,including two positive integers a(1≤a≤2*10^4),b(1≤b≤10^9),and their meanings are shown in the description.Contains most of the 12W test cases.
Output
For each set of input data,output a line of two integers,representing X, Y.If you cannot find such X and Y,output one line of "No Solution"(without quotation).
题意:给你两个数a,b如果能找到两个数x,y使得x+y=a而且x,y的最小公倍数为b。
由于题目给出数据组数下、较多有12w组所以遍历会超时,所以要想办法直接求值。
根据题意能得到两个公式:
(1)x+y=a;
(2)x*y=b*k;(k为x,y的最大公约数)
显然有一个k在这里不好求答案所以想办法把k除掉。
将(1)左右都除k得到
(3)x/k+y/k=a/k;
再将(2)左右都除k得到
(4)(x/k)*(y/k)=b/k;
由于k是x,y的最大公约数,所以x/k,与y/k互质。所以a/k,与b/k也是互质。
所以问题就简化到求
i+j=a/gcd(a,b),i*j=b/gcd(a,b);
i和j的解。
#include <iostream>
#include <cmath>
using namespace std;
int X , Y;
int gcd(int a , int b) {
return b > 0 ? gcd(b , a % b) : a;
}
int cal(int a , int b , int c) {
if(a * a - 4 * b < 0)
return 0;
int gg = a * a - 4 * b;
int fff = sqrt(gg);
if(gg != fff * fff) {
Y = -1 , X = -1;
return 0;
}
X = (a + fff);
Y = (a - fff);
if(X % 2 == 0 && Y % 2 == 0) {
X /= 2;
Y /= 2;
return 1;
}
else {
X = -1;
Y = -1;
return 0;
}
}
int main()
{
int a , b;
while(cin >> a >> b) {
int c = gcd(a , b);
X = -1 , Y = -1;
if(cal(a / c , b / c , c) && X != -1 && Y != -1) {
cout << min(X , Y) * c << ' ' << max(X , Y) * c << endl;
}
else {
cout << "No Solution" << endl;
}
}
return 0;
}
最新文章
- C#动态编译引擎-CS-Script
- DELPHI XE5
- 前端面试题 之 JavaScript
- 微型orm fluentdata
- win2008server系统下文件替换权限
- 在CentOS 6.4中编译安装gcc 4.8.1
- Contest2037 - CSU Monthly 2013 Oct (problem D :CX and girls)
- 把AS代码链接到fla文件
- hadoop2.2.0的ha分布式集群搭建
- Python 入门知识捡漏
- Android--使用剪切板在Activity中传值
- 使用python调用wps v9转换office文件到pdf
- 机器学习:Python实现聚类算法(二)之AP算法
- Java Socket实战之一 单线程通信基础socket
- bzoj3111: [Zjoi2013]蚂蚁寻路
- Jprofiler监控工具(内存泄漏)
- python基础之多线程锁机制
- php中怎么理解Closure的bind和bindTo
- Java基础知识:Java实现Map集合二级联动4
- js 获取中文的拼音首字母