数论题leetcode

【leetcode刷题】一道数论题

网络资讯 2023-01-19 21:11:35 26

导读

于是我写了个代码来跑,n=2到8都能很快找到,n=9开始就很慢了,10后面数就溢出了,我得改下代码。……

在刷leetcode题目:479. 最大回文数乘积的时候,发现一个问题,总结起来是这样的:

现在有一个2n位的回文数:abba,abccba,......例如1331,287782

证明2n位的回文数中一定有一个数能整除某一个n位的数,且整除的结果也是一个n位的数

例如n=2时,2n位的回文数从大到小依次是:

9999,9889,9779,......,1001,要证明这些数中一定有一个数,能表示为一个2位数乘一个2位数

显然,9001=99*91,因此,当n=2时,原命题成立

要证明对于n>=2时,原命题成立,或能找到一个反例来证明原命题不成立我想能不能找到一个例子使得原命题不成立,这样就不用证明了。于是我写了个代码来跑,n=2到8都能很快找到,n=9开始就很慢了,10后面数就溢出了,我得改下代码。

n=2,9009=99*91

n=3,906609=993*913

n=4,99000099=9999*9901

n=5,9966006699=99979*99681

n=6,999000000999=999999*999001

n=7,99956644665999=9998017*9997647

n=8,9999000000009999=99999999*99990001

n=9,999900665566009999=999980347*999920317

(PS:我试图证明的过程中找到一个结论:2n位的回文数一定有质因子11,不知道能不能用得上)(PPS:上次爆职业的时候发现好多福娃是程序员,所有发个帖子看有没有大佬能解答一下)