|
锁定老帖子 主题：关于万人开关门
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-06-14
shanga 写道 Crusader 写道 fivestarwy 写道 初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。 M=q1^n1*q2^n2*q3^n3......... 判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可 +1 +1,因子相同的看作一个 |
| 返回顶楼 | |
|
发表时间：2011-06-14
最后修改：2011-06-14
n号门是打开还是闭合，应该是看n的最大公约数的奇偶性，是奇数门是开着的，偶数门是关着的。
所以要先把1到10000的所有质数求出来。 |
| 返回顶楼 | |
|
发表时间：2011-06-14
shanga 写道 shanga 写道 Crusader 写道 fivestarwy 写道 初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。 M=q1^n1*q2^n2*q3^n3......... 判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可 +1 +1,因子相同的看作一个 仔细想了下，上面的‘因子相同的看作一个’是不对的 |
| 返回顶楼 | |
|
发表时间：2011-06-14
最后修改：2011-06-14
Crusader 写道 fivestarwy 写道 初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。 M=q1^n1*q2^n2*q3^n3......... 判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可 +1 每个数都去因式分解效率是很低的~其实这个问题就是在问一个数的除数有多少？对于这个问题，相对较好（应该还有不少优化空间）的解法就是楼主题目描述的方式。不过这个做法有个缺点就是占用空间较大。
int N = 10000000;
int[] count = new int[N];
for (int i =1; i < N; i++)
{
for (int f = i; f < N; f += i)
{
count[f]++;
}
}
这个算法的复杂度大概是O(NLOG(N))，但是他没有用到除法和乘法所以他要比对于N个数因式分解要快不少。 |
| 返回顶楼 | |
|
发表时间：2011-06-14
lzyzizi 写道
int N = 10000000;
int[] count = new int[N];
for (int i =1; i < N; i++)
{
for (int f = i; f < N; f += i)
{
count[f]++;
}
}
这个算法的复杂度大概是O(NLOG(N))，但是他没有用到除法和乘法所以他要比对于N个数因式分解要快不少。 因式分解时间复杂度O(sqrt(N)),总共复杂度也就是O(N*sqrt(N)),1.5次的多项式复杂度还是很好接受吧 |
| 返回顶楼 | |
|
发表时间：2011-06-14
fivestarwy 写道 lzyzizi 写道
int N = 10000000;
int[] count = new int[N];
for (int i =1; i < N; i++)
{
for (int f = i; f < N; f += i)
{
count[f]++;
}
}
这个算法的复杂度大概是O(NLOG(N))，但是他没有用到除法和乘法所以他要比对于N个数因式分解要快不少。 因式分解时间复杂度O(sqrt(N)),总共复杂度也就是O(N*sqrt(N)),1.5次的多项式复杂度还是很好接受吧，其中质数还可以打表，还有优化的空间 |
| 返回顶楼 | |
|
发表时间：2011-06-14
最后修改：2011-06-15
看来我也理解错了，重新理解一下
|
| 返回顶楼 | |
|
发表时间：2011-06-14
最后修改：2011-06-14
刚才回头看了下问题，发现有个地方很多人都理解错了，除数的奇偶性无法判断门的开关，因为只有奇除数是关门而偶除数是开门。。。
比如:4的除数 1,2,4。按照质因数分解的思路，他应该是关着的，但是仔细看题会发现2和4都是关门，也就是说1开门以后，2关门，4也关门。。。也就是说4根本不会关心当前门的状态，执行他所应该执行的动作，所以其实门开不开只由最后一个开关人的决定。 night_stalker 写道 哦，每个门只受最后一个碰它的人影响，最后一个碰它的人的号码和门相同。
1开2关3开4关5开6关⋯⋯ 所以结果就是奇数门开，偶数门关 ⋯⋯ 原来正解早就出现。。。 |
| 返回顶楼 | |
|
发表时间：2011-06-14
挺有意思哈
|
| 返回顶楼 | |
|
发表时间：2011-06-14
lzyzizi 写道 刚才回头看了下问题，发现有个地方很多人都理解错了，除数的奇偶性无法判断门的开关，因为只有奇除数是关门而偶除数是开门。。。
比如:4的除数 1,2,4。按照质因数分解的思路，他应该是关着的，但是仔细看题会发现2和4都是关门，也就是说1开门以后，2关门，4也关门。。。也就是说4根本不会关心当前门的状态，执行他所应该执行的动作，所以其实门开不开只由最后一个开关人的决定。 night_stalker 写道 哦，每个门只受最后一个碰它的人影响，最后一个碰它的人的号码和门相同。
1开2关3开4关5开6关⋯⋯ 所以结果就是奇数门开，偶数门关 ⋯⋯ 原来正解早就出现。。。 我也觉得这个解释已经对了。。不知道为什么还有那么多复杂的讨论 |
| 返回顶楼 | |
