首页 > 技术交流 > 心动网络×Taptap研发笔试题探讨

心动网络×Taptap研发笔试题探讨

头像
Beeeeeeeta
编辑于 2020-10-18 23:07:51 APP内打开
赞 0 | 收藏 0 | 回复1 | 浏览401
做了老长时间还没做出来,求有无大神指导一下:
题目:
给定两个正整数 ds,请找到另外两个正整数 ab满足以下条件:
1. a, b最大公约数为 d
2. a2 - b2 = s;
如果有多种可能的 ab,返回 a最大的一组。
输入要求:两个64位无符号正整数。
例子:
1. d=38, s=23104;
a=190, b=114.
2. d=20, s=12400;
a=320, b=300.
3 . d=1, s=27;
a=14, b=13.
我的思路:先判断 d是否为 1,如果为 1ab为互质数。两种情况,一种是 b=1,另外一个数就等于 (s+1)的平方根; b不为 1的话,就从 1开始,两个相邻的数的和等于 s的时候,循环结束。
d不为 1的情况下,循环从 1d的数 i,判断 s/d 2 +i 2的平方根 r是否为整数,如果是的话,判断 i*dr*d的最大公因数是否为d,如果是,再跟 maxA比较,如果大于 maxA,则 maxA等于这个r*d直到循环结束。
本来还考虑了 a b两个数除以 d的因数都大于 d ,但是我这一块的思路应该有问题不知道是不是循环过多还是算法复杂度太大加上会程序超时,最后也没有 AC. QAQ
蹲一个大佬康康分享下~~~谢谢!!!

1条回帖

回帖
加载中...
话题 回帖

相关热帖

技术交流近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐