先宰熊，再杀牛，周五猪，中期牛 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

先宰熊，再杀牛，周五猪，中期牛

先宰熊，再杀牛，周五猪，中期牛# Stock

r*t2010-06-15 07:06

1 楼

N是一个很大的正整数——可能到10^15次方，
简单起见，不考虑溢出，或者假设用python
A 是一个array，里面存着一些正整数，up to 1000个
从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
举个例子：
N = 10
A = [2,4,5]
那么返回4 (1,3,7,9满足条件)
我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
def left(N = 10, A = [2,4,5]):
ones = [1 for i in xrange(N+1)]
ones[0] = 0
for inte in A:
if inte == 1:
return 0
for i in xrange(1,N/inte+1):
ones[i*inte] = 0

return sum(ones)

e*e2010-06-15 07:06

2 楼

数钱数到嘴抽筋的时刻不远了，哦哈哈哈哈

w*n2010-06-15 07:06

3 楼

是不是可以先处理一下A？比如有2的时候4就没必要了

s*r2010-06-15 07:06

4 楼

咋赚的？

h*t2010-06-15 07:06

5 楼

如果N很大的话你可以先找1-10000有多少数不能被A中的任何一个数整除的，接着找
10001-20000。。。。

e*e2010-06-15 07:06

6 楼

let's see after close bell on this coming Thursday, hehe
celebrate first

【在 s*****r 的大作中提到】

: 咋赚的？

h*c2010-06-15 07:06

7 楼

我觉得
先处理A成B, for any b_i in B，it has no multiple in B
for any b_i in B
c_i = N div b_i
sigma_c = sigma_c + c_i
return N - sigma_c

【在 r*****t 的大作中提到】

: N是一个很大的正整数——可能到10^15次方，
: 简单起见，不考虑溢出，或者假设用python
: A 是一个array，里面存着一些正整数，up to 1000个
: 从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
: 举个例子：
: N = 10
: A = [2,4,5]
: 那么返回4 (1,3,7,9满足条件)
: 我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
: def left(N = 10, A = [2,4,5]):

s*r2010-06-15 07:06

8 楼

肯定大瀑布了

【在 e*****e 的大作中提到】

: let's see after close bell on this coming Thursday, hehe
: celebrate first

s*d2010-06-15 07:06

9 楼

how about there's one number = b[i]*b[j]? you will count it twice. The hard
part of this question is how to eliminate these duplicates...

【在 h**********c 的大作中提到】

: 我觉得
: 先处理A成B, for any b_i in B，it has no multiple in B
: for any b_i in B
: c_i = N div b_i
: sigma_c = sigma_c + c_i
: return N - sigma_c

e*e2010-06-15 07:06

10 楼

I would like to see a modest 10% retreat

【在 s*****r 的大作中提到】

: 肯定大瀑布了

x*32010-06-15 07:06

11 楼

这个是不对的，比如Ａ［２，３］，　Ｎ＝６，你的结果是１，但应该是２。因为６除
了两次。就算你在结果里把Ｎ／２＊３加到结果里，结果依然有问题。
我是没想到比较好的方法，有人有比较好的办法吗？

【在 h**********c 的大作中提到】

: 我觉得
: 先处理A成B, for any b_i in B，it has no multiple in B
: for any b_i in B
: c_i = N div b_i
: sigma_c = sigma_c + c_i
: return N - sigma_c

h*c2010-06-15 07:06

12 楼

yes, there is miss
TBD

hard

【在 s******d 的大作中提到】

: how about there's one number = b[i]*b[j]? you will count it twice. The hard
: part of this question is how to eliminate these duplicates...

h*c2010-06-15 07:06

13 楼

那用个search tree
把A 的element 按divisible 关系做成树
用树来漏1-N
space is A space
仅供参考，低调

w*d2010-06-15 07:06

14 楼

Consider the simplest case: A={2}, then any odd number below N is OK, so the
result would be (N - N/2). Then consider A={2, 3}, any number below N that
is not mutiply of 2 or 3 is OK, so the result would be (N - N/2 - N/3 + N/6)
. Then consider A={2, 3, 5}, the result would be (N - N/2 - N/3 - N/5 + N/6
+ N/10 + N/15 - N/30).
So there is a general rule:
for A={a1, a2, ..., aN}, if ai is not dividable by aj for any i != j, then
we could:
1. for i from 1 to N, calc r1 = N - SUM(N/ai);
2. for i, j from 1 to N, i != j, calc r2 = r1 + SUM(N/(ai*aj));
3. for i, j, k from 1 to N, i != j != k, calc r3 = r2 - SUM(N/(ai*aj*ak));
...
until all numbers in A are chosen.
then the final rN is the result.
So for the problem, first we preprocess A to eliminate any multiplies in A.
For example, A={2, 4, 5}, we can eliminate 4 because it is a mutiply of 2
which is also in A. So A'={2, 5}, then we calc:
r1 = 10 - 10/2 - 10/5 = 10 - 5 - 2 = 3;
r2 = r1 + 10/10 = 3 + 1 = 4;
then the final result is 4.

t*52010-06-15 07:06

15 楼

mark

h*22010-06-15 07:06

16 楼

你怎么eliminate any multiples
2和4这种还好
4和6这种怎么做？求最大公约数？

the
that
6)
6

【在 w*****d 的大作中提到】

: Consider the simplest case: A={2}, then any odd number below N is OK, so the
: result would be (N - N/2). Then consider A={2, 3}, any number below N that
: is not mutiply of 2 or 3 is OK, so the result would be (N - N/2 - N/3 + N/6)
: . Then consider A={2, 3, 5}, the result would be (N - N/2 - N/3 - N/5 + N/6
: + N/10 + N/15 - N/30).
: So there is a general rule:
: for A={a1, a2, ..., aN}, if ai is not dividable by aj for any i != j, then
: we could:
: 1. for i from 1 to N, calc r1 = N - SUM(N/ai);
: 2. for i, j from 1 to N, i != j, calc r2 = r1 + SUM(N/(ai*aj));