📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2088| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

T家数学题

全局:
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)


上一篇:用Rolling hash写strStr时遇到了一个奇怪的问题,求解。
下一篇:【求助】求教POCKET GEMS必考题【成就系统设计】
🔗
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;
}

谢谢搂主分享
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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