HDU - 5974 A Simple Math Problem (数论解方程)

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).

Sample Input

6 8
798 10780

Sample Output

No Solution
308 490

题意:

给出a, b,求出一组x, y使得 x + y = a 且 lcm(x, y) = b

思路:

显然不能暴力

有个结论https://blog.csdn.net/protecteyesight/article/details/72935030

大体是这样:gcd(x, y) = gcd(x + y, lcm(x, y))

下面开始列式子

a = x + y

b = lcm(x, y)

gcd(x, y) = gcd(x + y, lcm(x, y)) = gcd(a, b)

x * y = gcd(x, y) * lcm(x, y) = gcd(a, b) * b

x + y = a

联立上面加粗的这俩式子,解方程就好惹

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    ll a = 50, b;
    while(~scanf("%lld%lld", &a, &b))
    {
        ll t = b * gcd(a, b);
        t = a * a - 4 * t;
        bool flag = 1;
        if(t < 0)
        {
            flag = 0;
        }
        else
        {
            ll tmp = sqrt(t);
            if(tmp * tmp != t)
                flag = 0;
            else
            {
                ll x = a - tmp;
                if(x % 2)
                {
                    x = a - tmp;
                    if(x % 2)
                        flag = 0;
                    else
                    {
                        x /= 2;
                        cout<<x<<' '<<a - x<<'\n';
                    }
                }
                else
                {
                    x /= 2;
                    cout<<x<<' '<<a - x<<'\n';
                }
            }
        }
        if(!flag)
            cout<<"No Solution"<<'\n';
    }
    return 0;
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务