Question

杭电1098题求思路最好具体点...不要源代码...谢谢...

Answer 1

既然不要源代码，那我就讲讲我的想法，我觉得要用到初等数论里的费马小定理和中国剩余定理先做化简。

这个数学过程比较麻烦，我写了好久，所以如果你没有耐心看，请直接看最后两段，会告诉你怎么编程。

f(x)=5*x^13+13*x^5+k*a*x=x(5*x^12+13*x^4+k*a)，这个函数的形式直接就是费马小定理的形式

从百科抄来的，需要深究请查百科费马小定理
费马小定理是数论中的一个重要定理,其内容为: 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1

对f(x)=x(5*x^12+13*x^4+k*a)用此定理分析：
（1）如果x是65的倍数，那么已经符合65整除f(x)
（2）如果x是5的倍数，只要5*x^12+13*x^4+k*a被13整除即可，去掉13的倍数13*x^4，也即5*x^12+k*a被13整除，由费马小定理，5与13互质，13是质数，所以x^(13-1)模13余1，所以5*x^12模13余5，要使5*x^12+k*a被13整除，k*a必须模13余8(k*a≡8(mod 13))
（3）如果x是13的倍数，类似（2），需要13*x^4+k*a被5整除，由费马小定理类似得到x^4模5余1，所以13*x^4模5余3，k*a必须模5余2(k*a≡8(mod 13))
（4）如果x不含5和13这两个因子，则需要5*x^12+13*x^4+k*a被65整除了，等价于既要被5整除，又要被13整除，就相当于以上(2)(3)两种情况的条件要同时满足，所以有
k*a≡2(mod 5) 并且 k*a≡8(mod 13)

怎么解这种方程呢？就要用到中国剩余定理。当然这是手算，你大可以用以上几个条件用if else 语句在1-10000之间穷举。用中国剩余定理就是为了减少运算量，要深究就查百科吧，很详细。
找到最小的正整数m，使得5*m≡1(mod 13)，找可能的数试几下得到m=8
再找最小的正整数n，使得13*n≡1(mod 5)，找可能的数试几下得到n=2
根据中国剩余定理，先找到最小的k*a，然后在此基础上任意加减65的倍数都是满足的，这个k*a=40*8+26*2-65*5=47
得到k*a通式为
k*a=47+65*r (r为任意自然数)

你可以验证题目下给的几个有答案的输入示例都是满足这个条件的，所以经过一系列数学化简后，这个问题很简单，就是判断给定的k值有没有a使得k*a=47+65*r（r为任意自然数），并找出最小的。

判断存在性，可以把a从1取到10，判断个位数是否有可能为2或者7（k*a=47+65*r的个位数只能是2或者7），之后找最小数就简单了，对r作for循环，从0开始，不断判断是否能被k整除，直到可以就找到了。

我也没动手把程序编出来，所以这个思路不一定十分完善，有问题欢迎探讨。

追问

非常感谢啊....很具体详细...
我写了一下代码...已经AC了..
不过我觉得直接用费马小定理就够了....因为那个剩余定理我不是很明白...而且应该不用在1-10000之间穷举吧...在1-64就可以了..
for(i=1;i<=64;i++)
if((i*k)%5==2&&(i*k)%13==8)
...总之是在是太感谢你了...