一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 465|回复: 4
收起左侧

[算法题] T家数学题

[复制链接] |试试Instant~ |关注本帖
ccgogo123 发表于 2015-5-7 09:26:05 | 显示全部楼层 |阅读模式
5小米
You are given two integers, M and N, count the pairs (A,B) where:
1<= A <= M
1<= B <= N.鏈枃鍘熷垱鑷�1point3acres璁哄潧
(A^(1/3) + B^(1/3)) ^ 3 is an integer.


Sample:
M = 1, N = 8 -> 2
(1, 1), (1, 8)

stellari 发表于 2015-5-7 11:08:25 | 显示全部楼层
请问A,B是否也必须是Integers?
回复

使用道具 举报

 楼主| ccgogo123 发表于 2015-5-9 00:00:29 | 显示全部楼层
stellari 发表于 2015-5-7 11:08
请问A,B是否也必须是Integers?

对,都是整数。请问有什么思路吗?可以讨论讨论。。。。。
回复

使用道具 举报

stellari 发表于 2015-5-9 10:15:29 | 显示全部楼层
stellari 发表于 2015-5-7 11:08
请问A,B是否也必须是Integers?

满足条件的A和B应该只有下列两种情况

1. A和B都是完全立方数,如1,8,27,64
2. A和B都是完全立方数的k倍,如24和81,分别是8和27的3倍。

所以最笨的办法是(当然我目前还没想出更聪明的办法):

对1~M之间的每个数 i
1. 将 i 开立方并化简成形如a*cubicroot(b)的形式 (即a^3* b = i);
2. 在1~N中数出所有符合 p * b形式的数 (其中p是一个完全立方数)的个数 d;
3. sum += d;

比如,M = 100, N = 50
对于1~100间的一个数字,例如54
开立方可化简为3 * cubicroot(2),
那么在1~50间找所有的1 * 2, 8 * 2, 27 * 2, 64 * 2...
27 * 2就已经超过了50,所以能和A = 54配对的 B只有 1*2 = 2, 8*2 = 16两种。


回复

使用道具 举报

nano 发表于 2015-5-15 04:19:19 | 显示全部楼层
假设A和B的最大公约数为C

A=C*A'
B=C*B'

只需保证(A'^(1/3)+B'^(1/3))^3是整数,考虑
A'和B'均为任意正整数的三次幂,则一定满足条件

似乎不用考虑负数,相对比较不那么麻烦,同时也可以证明小数的整数次方不会是整数,将小数写作整数和纯小数相加的形式然后多项式相乘展开,可以发现最高次项带来小数点后最多位是不会被消除的。

我的ugly实现如下,

#include <iostream>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution{
unordered_set<int> cube_list;
int max_cube_root;
int gcd(int A, int B){
        int C=0;
        while(A){
                C=A, A=B%A,B=C;
        }
        return B;
}

void resetCubeList(int upper_bound){
        int i = max_cube_root,cur_boundary =0;
        for(;cur_boundary<=upper_bound;++i, cur_boundary=i*i*i){
                cube_list.insert(cur_boundary);
        }
        max_cube_root=i-1;
}

public:
Solution(){
    max_cube_root=0;
    cube_list={};
}
bool isStillAnInteger(int A, int B, int M, int N){
        if(max(M,N)>max_cube_root*max_cube_root*max_cube_root)
                resetCubeList(max(M,N));
        int max_divisor=gcd(A,B);
        A=A/max_divisor, B=B/max_divisor;
        return cube_list.count(A) && cube_list.count(B);
}
};

int main(void){
Solution s;
if(s.isStillAnInteger(2,17,10,20))
cout<<"it is true!"<<endl;
else
cout<<"I really do not think so...."<<endl;

return 0;
}

谢谢搂主分享
回复

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 21:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表