M*a
1 楼
就是给个数组A都是正整数，然后一个范围[1,N]，返回[1，N]当中不能被任何A的元素
整除的数字的个数。
就这么简单，怎么做。
什么一个一个除着看的做法就不用说了。
整除的数字的个数。
就这么简单，怎么做。
什么一个一个除着看的做法就不用说了。
g*o
2 楼
能被任何A的元素整除?
你是说互质吗？
有公式
http://en.wikipedia.org/wiki/Euler's_totient_function
你是说互质吗？
有公式
http://en.wikipedia.org/wiki/Euler's_totient_function
M*a
3 楼
不能被任何A的元素整除
还要公式。。。估计就不是这么做了。
【在 g****o 的大作中提到】
: 能被任何A的元素整除?
: 你是说互质吗？
: 有公式
: http://en.wikipedia.org/wiki/Euler's_totient_function
还要公式。。。估计就不是这么做了。
【在 g****o 的大作中提到】
: 能被任何A的元素整除?
: 你是说互质吗？
: 有公式
: http://en.wikipedia.org/wiki/Euler's_totient_function
A*g
4 楼
如果A小，N大
找出A里最大和最小，和N比一下，然后把A里的每个数都从1开始找倍数，然后从[1,N]
里拿走
找出A里最大和最小，和N比一下，然后把A里的每个数都从1开始找倍数，然后从[1,N]
里拿走
l*b
5 楼
应该是假设A unsorted吧 有个不太好的思路 需要大概O（n）时间 和O（n）空间 但是
感觉空间还可以优化 我先说下思路：
把1-N所有N个数放进一个set 然后遍历A数组 假设A = {6,7, 9,2} (是不是A里要是有1
就可以直接返回0了) A[0] = 6， 所有就把6从set里删除（在6 < n的前提下）。。然
后 遍历所有6的倍数 知道这个倍数大于N了 就结束 继续下一个。。
好吧。。时间复杂度好像不止O（n - -|||）
感觉空间还可以优化 我先说下思路：
把1-N所有N个数放进一个set 然后遍历A数组 假设A = {6,7, 9,2} (是不是A里要是有1
就可以直接返回0了) A[0] = 6， 所有就把6从set里删除（在6 < n的前提下）。。然
后 遍历所有6的倍数 知道这个倍数大于N了 就结束 继续下一个。。
好吧。。时间复杂度好像不止O（n - -|||）
l*8
6 楼
1. 求A的最小公倍数x
2. for i = 1.. N
if GCD(i, x) == 1
print i
【在 M*******a 的大作中提到】
: 就是给个数组A都是正整数，然后一个范围[1,N]，返回[1，N]当中不能被任何A的元素
: 整除的数字的个数。
: 就这么简单，怎么做。
: 什么一个一个除着看的做法就不用说了。
2. for i = 1.. N
if GCD(i, x) == 1
print i
【在 M*******a 的大作中提到】
: 就是给个数组A都是正整数，然后一个范围[1,N]，返回[1，N]当中不能被任何A的元素
: 整除的数字的个数。
: 就这么简单，怎么做。
: 什么一个一个除着看的做法就不用说了。
相关阅读
明天Onsite，也来真心求祝福Software Developer Opening in Bay Area几个湾区工作机会，年底机会不多，大家抓紧。"Hacking a G Interview"怎么有这样低级错？汇报一下吧怎样判定是否绿卡广告急问，OPT 转F2错过了deadline 怎么办？Does someone can update their Export license application timing? Thanks.Onsite选周几好？刚刚onsite 求祝福最近没什么BL的面经？Amazon电面问一道C# interview testing quesiton看来做IT还真是让人瞧不起?考前不猜题，全面总复习？反interleave该怎么做？明年4月再申请H1B是不是生效期就是2013年10月1日了Phone interview next weekAmazon onsite 回来两天了，还没消息，求祝福。。为啥做IT软件让人瞧不起？