应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿九题：有多少不同的项?
313/4返回列表上一页1234下一页
查看: 2029  |  回复: 30
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-19 13:23:38
引用回帖:
Originally posted by sudo at 2011-06-18 23:00:09:
嗯，里面的magic number都是可以手工算出来的（不是我瞒天过海哦），计算过程和意义省略了...让大家猜猜看吧

原理类似因子分解，嗯

[code]
#include <stdio.h>

int tag[101];

int main(){
...

你这个很狠啊，俺来揭蒙面代码！
首先嘛，当然要说，乘方的规则长酱紫：
a^b=(a^m)^n=>b = m*n
根据这个，就可以得出来，2在100以内的乘方系数有5个，3在100以内系数有3个，如下：
2^6 = 64
3^4 = 81
4^3 = 64
5^2 = 25
6^2 = 36
7^2 = 49
8^2 = 64
9^2 = 81
10^2 = 100
之后就不可能再有乘方超过2的了
然后，根据上面的乘方算术，如果b = m*n，则会产生相同的数字，因此，当m取2的时候，对于值域为2~100的b，n允许有49个值，所有的对应关系如下：
m    2      3      4      5      6
n    49    33    25     20    16
于是，当系数是2的时候，上面的9个数都会产生49个重合的值，系数是3的时候，只有234会产生33个重合的值，系数是4的时候，23会产生重合的值，系数是56的时候只能是2，会产生20+16个重合的值，这些值重合的原因都是诸如：2^18 = 4^9
嗯，于是把所有数相加，就是所有重合的值：9*49+3*33+2*25+20+16 = 626，注意到2、4和8的关系，8^2=(2^3)^2=(2^2)^3=4^3，4^2=(2^2)^2=2^4，4^3=(2^3)^2=(2^2)^3，第一个重复计算了3次，第二个重复计算了2次，第三个重复计算了3次，看起来重复计算了8次，所以重复的数有：626-8=618，最终结果就是99*99-618。
然后，再来配数，嗯，第一个看起来对号了，第二个就是49+49了，第三个嘛，经验算，是49+33+25，第四个往没正经了，头疼，早安~
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
21楼2011-06-19 00:40:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by huycwork at 2011-06-19 00:40:36:
你这个很狠啊，俺来揭蒙面代码！
首先嘛，当然要说，乘方的规则长酱紫：
a^b=(a^m)^n=>b = m*n
根据这个，就可以得出来，2在100以内的乘方系数有5个，3在100以内系数有3个，如下：
2^6 = 64
3^4  ...

早安~

啊呀，我还没注意到10^2就是100了...那循环还可以更小...
赞一下(1人) 回复此楼
22楼2011-06-19 09:00:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by qinghuoly at 2011-06-19 00:18:03:
J语言啊，APL语言的替代版。

代码简洁精炼，够cool。话说欧拉工程上好多题目都有相应的J语言解法。

看了一下，确实非常简练，很geek的感觉~

估计我是学不会了...
赞一下(1人) 回复此楼
23楼2011-06-19 09:03:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-19 13:23:17
引用回帖:
Originally posted by sudo at 2011-06-19 09:00:44:
早安~

啊呀，我还没注意到10^2就是100了...那循环还可以更小...

昨晚想错了，哎~
2能够产生的重复数应该这么算：
2^2~4，产生49个重复的4^b
2^3~8，产生33个重复的8^b
2^4~16，产生25个重复的16^b，
同时4^2~16，产生49个重复，形如4^a=16^b
2^5~32，产生20个重复的32^b
2^6~64，产生16个重复，同时8^2~64，产生49个重复，4^3~64，产生33个重复
还有就是，原先包含在2^4~16里面的16^b，在4^2~16里面又被删了一遍，它们是16^2，16^4，16^8，16^16，同样，在2^6~64的64^b，在8^2~64里面删了一遍，是64^2，64^4，64^8，4^3~64里面则是64^8，所以全部加起来减去重复计算过的，就印证了启示，2产生的重复数有266个，哎，真是死脑细胞的活儿啊~
其余的做法也类似了，
3^2~9，
3^3~27，
3^4~81，同时9^2~81。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
24楼2011-06-19 10:47:16
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-19 13:23:03
引用回帖:
Originally posted by huycwork at 2011-06-19 10:47:16:
昨晚想错了，哎~
2能够产生的重复数应该这么算：
2^2~4，产生49个重复的4^b
2^3~8，产生33个重复的8^b
2^4~16，产生25个重复的16^b，
同时4^2~16，产生49个重复，形如4^a=16^b
2^5~32，产生20个重复的32 ...

咳，关键还是在于：什么情况下可能会有重复？先给出结论：

对于a, b而言，指数在[m, n]区间里面取整数，那么可能与a求幂后存在重复的b为
b = a^2, a^3, ..., a^p

这个很好理解，想象一下a, b因数分解之后的样子，举个例子
CODE:
     2   3   5   7   11 ...
a |  1   0   1   0    0  ...
b |  2   0   2   0    0  ...

显然只有这个指数向量正好是整倍数时，a和b的分别若干次幂之后才会有相等的可能

那么算法就变成了简单的寻找[2, 100]内的a的所有幂的数量，而对于不同的a，造成重复的个数的计算方法却是一样的（从因数分解表的角度看很容易明白）

然后问题继续简化：

如果a在范围内所有次幂只有1个，那么无重复：
1 x {2, 3, 4, ..., 100}

如果a在范围内所有次幂有2个，那么重复数相当于找出下面两行数字的重复个数：
1 x {2, 3, 4, ..., 100}
2 x {2, 3, 4, ..., 100}

如果a在范围内的所有次幂有3个，那么重复数相当于找出下面3行数字的重复个数：
1 x {2, 3, 4, ..., 100}
2 x {2, 3, 4, ..., 100}
3 x {2, 3, 4, ..., 100}

......

在[2, 100]中，最多的就是2的所有次幂数了，一共有6个，重复数相当于下面6行数字的重复个数：
1 x {2, 3, 4, ..., 100}
2 x {2, 3, 4, ..., 100}
3 x {2, 3, 4, ..., 100}
4 x {2, 3, 4, ..., 100}
5 x {2, 3, 4, ..., 100}
6 x {2, 3, 4, ..., 100}

这些都是容易手算出来滴~~~

[ Last edited by sudo on 2011-6-19 at 11:06 ]
赞一下(2人) 回复此楼
25楼2011-06-19 11:05:03
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-19 13:22:52
唉，这么一来，这个问题全部靠手算都可以出来了...
赞一下(2人) 回复此楼
26楼2011-06-19 11:11:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qinghuoly

木虫 (正式写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-19 13:22:28
引用回帖:
Originally posted by sudo at 2011-06-19 09:03:45:
看了一下，确实非常简练，很geek的感觉~

估计我是学不会了...

有兴趣就一起学吧，我也就刚学了一个月。
wiki词条给出的中文参考资料
http://faculty.ndhu.edu.tw/~pkuo/computer/Jyuyen.pdf
http://faculty.ndhu.edu.tw/~pkuo/computer/dicttw/main.htm

去欧拉计划做题吧，做对了就去看人家的J语言解法。
赞一下(2人) 回复此楼
天地为帐，日月为灯，风雷为号角，云虹为旗令，山川为阵图，草木为兵卒。运阴阳五行为谋，策古今兴替为略。
27楼2011-06-19 12:31:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-19 13:22:15
引用回帖:
Originally posted by sudo at 2011-06-19 11:05:03:
咳，关键还是在于：什么情况下可能会有重复？先给出结论：

对于a, b而言，指数在[m, n]区间里面取整数，那么可能与a求幂后存在重复的b为
b = a^2, a^3, ..., a^p

这个很好理解，想象一下a, b因数分解 ...

啊？你不会直接从矩阵里面择吧？
我纠结的问题在于指数部分还有递归，递归里面又有重复。哎~俺滴脑细胞~可怜了。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
28楼2011-06-19 12:38:53
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by huycwork at 2011-06-19 12:38:53:
啊？你不会直接从矩阵里面择吧？
我纠结的问题在于指数部分还有递归，递归里面又有重复。哎~俺滴脑细胞~可怜了。

似乎我没有解释清楚啊

哪来的递归......

算啦，天气热，都休息休息吧，别想了
赞一下(1人) 回复此楼
29楼2011-06-19 13:55:38
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by qinghuoly at 2011-06-19 12:31:45:
有兴趣就一起学吧，我也就刚学了一个月。
wiki词条给出的中文参考资料
http://faculty.ndhu.edu.tw/~pkuo/computer/Jyuyen.pdf
[url]http://faculty.ndhu.edu.tw/~pkuo/computer/dicttw/main.ht ...

等某一天有动力了再说~天气太热，不适合动脑筋...
赞一下(1人) 回复此楼
30楼2011-06-19 14:00:05
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
313/4返回列表上一页1234下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭