开发者社区人工智能文章正文

3045 Lcm与Gcd构造

2022-06-07 128

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 已知：gcd(a,b) = nlcm(a,b) = m求min(a,b)是多少通过gcd的了解我们可以知道，两个数a == k1 * n以及b == k2 * n并且gcd(k1,k2) == 1ab == n * mm == a * b/nab == k1 * k2 * n * n于是可以得到 m == k1 * k2 * n将n除到左边，可以得出m/n == k1 * k2于是k1 和 k2 都是 m / n的因子这样就可以以根号的复杂度找出这两个因子，并判断k1 和 k2 是否是互质的a + b == (k1 + k2 ) * n所以说代码：

已知：

gcd(a,b) = n

lcm(a,b) = m

求min(a,b)是多少

通过gcd的了解我们可以知道，两个数a == k1 * n以及b == k2 * n并且gcd(k1,k2) == 1

ab == n * m

m == a * b/n

ab == k1 * k2 * n * n

于是可以得到 m == k1 * k2 * n

将n除到左边，可以得出m/n == k1 * k2

于是k1 和 k2 都是 m / n的因子

这样就可以以根号的复杂度找出这两个因子，并判断k1 和 k2 是否是互质的

a + b == (k1 + k2 ) * n

所以说代码：

  int t = read;
    while(t--){
        ll n = read,m = read;
        ll lim = m / n;
        ll t1,t2;
        ll ans = 0x3f3f3f3f;
        for(ll i=1;i*i<=lim;i++){
            if(lim % i == 0){
                t1 = i,t2 = lim / i;
                if(gcd(t1,t2) == 1) ans = min(ans,(t1+t2)*n);
            }
        }
        printf("%lld\n",ans);
    }