A Simple Math Problem（HDU-5974）

r囧r小猫 2022-05-19 14:34 194阅读 0赞

**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**  
I nput includes multiple sets of test data.Each test data occupies one line,including two positive integers a(1≤a≤2\*104),b(1≤b≤109),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).

**Sample Input**  
6 8  
798 10780  
**Sample Output**  
No Solution  
308 490

***题意：***  
输a,b，找出一个x 和 y 满足 x+y=a，lcm（x,y)=b;  
令 x*y = b*gcd(x,y);  
设 gcd(x,y) = d;  
x =i \* d;  
y = j \* d;  
a = (i + j)*d;  
b = i*j*d;  
gcd(a,b) = d; （推导结论）  
x*y = b\*gcd(a,b);  
x + y = a;  
解一元二次方程可得解  
**代码如下：**

#include<iostream>
    #include<math.h>
    using namespace std;
    
    int gcd(int m,int n){ 
    	return n==0?m:gcd(n,m%n);
    }
    int main(){ 
    	int a,b,i,j,x,y;
    	while(scanf("%d %d",&a,&b)!=EOF){ 
    		int c=gcd(a,b);
    		int del=a*a-4*b*c;
    		if(del<0){         //无解 
    			printf("No Solution\n");
    			continue;
    		}
    		int q=sqrt(del);
    		if(q*q!=del||(a-q)%2!=0){ 
    			printf("No Solution\n");
    			continue;
    		}
    		x=(a-sqrt(del))/2;
    		y=a-x;
    		printf("%d %d\n",x<y?x:y,x<y?y:x);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，194人围观）

还没有评论，来说两句吧...

相关阅读

相关 A Simple Math Problem HDU - 1757(矩阵快速幂优化递推)

题目连接][Link 1] 对于这种题，只要构造出矩阵（可能每个构造出的矩阵不同），然后用矩阵快速幂去递推。要注意的是矩阵乘法没有交换律。本人很懒不做解...

﹏ヽ暗。殇╰゛Y/ 2024年04月17日 20:45/ 0 赞/ 73 阅读

相关 a simple example rabbitMQ

此rabbitMQ 版本3.2.2： package com.miracle.queue; import java.io.IOExcept

布满荆棘的人生/ 2022年09月20日 15:09/ 0 赞/ 179 阅读

相关 A Simple Task

A Simple Task Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 Give

我不是女神ヾ/ 2022年08月18日 02:22/ 0 赞/ 202 阅读

相关 A Simple Math Problem（HDU-5974）

Problem Description Given two positive integers a and b,find suitable X and Y to meet t

r囧r小猫/ 2022年05月19日 14:34/ 0 赞/ 195 阅读

相关杭电 1757 A Simple Math Problem （矩阵快速幂）

题目链接：[点我][Link 1] Problem Description Lele now is thinking about a simple function f(

小咪咪/ 2022年05月16日 13:05/ 0 赞/ 188 阅读

相关 A simple smb.conf sample

You don't need much time on samba, just reference the following smb.conf. But please re

淡淡的烟草味﹌/ 2022年05月16日 09:23/ 0 赞/ 170 阅读

相关 HDU1757 A Simple Math Problem——————矩阵快速幂

A Simple Math Problem Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/3276

矫情吗；*/ 2022年05月09日 11:12/ 0 赞/ 178 阅读

相关（比赛）A - Simple String Problem

A - Simple String Problem Time Limit:10000MS Memory Limit:65536KB 64bit IO Format:%ll

蔚落/ 2021年12月21日 09:09/ 0 赞/ 244 阅读

相关【2016ACM/ICPC亚洲区大连站D】HDU - 5974 A Simple Math Problem 数论推公式

题意 x+y=a lcm(x,y)=b 求x,y 12WCases + b 10^9 + a 10^4 http://acm.hdu.edu.cn/showprobl

我不是女神ヾ/ 2021年12月03日 18:51/ 0 赞/ 173 阅读

相关 HDU - 5974 - A Simple Math Problem 【数论】题解

目录 1.题目 2.代码 1.题目 Given two positive integers a and b,

电玩女神/ 2021年07月25日 00:18/ 0 赞/ 356 阅读