| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1264 人关注过本帖
标题:出现了 TLE 怎么办 《YEAR,我就想吃苹果》
只看楼主 加入收藏
光头强
Rank: 1
等 级:新手上路
帖 子:34
专家分:0
注 册:2015-10-1
收藏
得分:0 
回复 3楼 beyondyf
谢啦
2015-11-18 18:00
光头强
Rank: 1
等 级:新手上路
帖 子:34
专家分:0
注 册:2015-10-1
收藏
得分:0 
回复 10楼 wfoo
大一新生 刚学 表示还不懂
2015-11-18 18:02
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
以下是引用wfoo在2015-11-18 16:28:59的发言:

这个题目其实还有纯数学上的思路,
An = 111111..1  = 10**(n-1) + 10**(n-2) + ... 1 = (10**n - 1) / 9,
An mod n = 0的问题完全可以转化为 10**n == 1 mod m,(m的值由n决定,m=n或m=3*n或n=9*n)
欧拉定理: 若m,a互素,则a ** φ(m) == 1 mod m,
这样的话至少φ(m)是能满足条件的,至于是不是最小的那个数,我没去证明过。

知道欧拉定理很不错,不过我更想看到你如何实际应用它。展示代码我送你100专家分。觉得不够还可以再加。

另外,我分析时还真没你想的那么复杂,只如risp所言不过是列个竖式而已,只不过省略了不必要的部分。

重剑无锋,大巧不工
2015-11-19 18:30
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
如果只要得到 t = t % n * 10 + 1 这个式子,我觉得可以看出来,连竖式都不要,用同余的表达式让人好理解。或者换个角度想,如果不是10进制,是13进制又或者是12889,。。。再用竖式推出类似的式子看看,但是用我的方法一样可以看出来。

根据我上面用欧拉定理的推导,其实可以发现,不管是多少进制,10,12889.。。,只要和n互质,φ(m)总是能满足条件的,但很容易发现它不是最小的那个数。还有1个定理
若t为a对模n的阶,s为某一正整数,满足a**s = 1 (mod n),则s必为t的倍数
所以要求的那个最小正式肯定是φ(m)的倍数。比如
n=11时,   φ(m) = φ(11) = 11 - 1 = 10 = 2 * 5,最小的整数只能是2,5,10,很容易发现2满足条件。
n=3时,    φ(m) = φ(9*3) = 3**3 = (3-1) * 3**2 = 18,最小的整数只能为2,3,6,9,12,18,很容易发现3满足条件。
n=21时,   φ(m) = φ(3*7) = (3-1)*(7-1) = 2*3*3,最小的整数只能为2,3,6,9,12,18,很容易发现6满足条件。
n=231时,  φ(m) = φ(9*3*7*11) = (3-1)*3**2 * (7-1) * (11-1) = 6 * 10 * 2 * 9 = 2 * 5 * 3**3 * 2**2,很显然 2**2可以去掉,所以这个数为2*5*3**3,
            最小整数只能为(3,9,27,5,15,45,145),2*(3,9,27,5,15,45,145),至于是哪个数我没去算过。

这里面的推导,应该还可以去掉一些不必要的情况。所以这题可以转换为因式分解。
代码不想写,一写代码就发愁。我只是觉得这是一个思路,并不是说性能比用最简单的for循环要好,如果要我写代码,估计也会写出你提供的那个。通常境况下,或者是超大数,这个方法的性能也是很好的。
2015-11-20 10:08
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
口可口可,这就是问题所在了,你的方法作为应用并不实用。当然拿出来探讨可以。目前数论领域可以应用于计算的结论只有那么几个。

重剑无锋,大巧不工
2015-11-20 16:06
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
不是不实用,而是没不要用。如果把10进制改为1千多位的进制i,把n也改为1千多位,你还会直接用循环来做么。如果分解因式把质数保存起来,指数幂求模有快速算法,中间值也保存起来,这种方法性能比较不错的。并且我觉得上面的结论还可以进一步优化化简。在int下谁会浪费时间弄这种代码。
2015-11-20 17:49
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
好啦,别抬扛啦。这个论坛里就有我写的大数对大数除法的模块。至于因式分解,别说1千多位,十进制50位的数以现在计算机的能力你有生之年都未必能分解完。

我很愿意讨论算法方面的问题,更注重理论与实践的结合。如果你愿意将你的想法实现为代码,还请不吝赐教,我必虚心学习。不愿意也不勉强。空谈就到此为止吧。

重剑无锋,大巧不工
2015-11-20 19:09
快速回复:出现了 TLE 怎么办 《YEAR,我就想吃苹果》
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018719 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved