HDU Ignatius's puzzle

链接

[http://acm.hdu.edu.cn/showproblem.php?pid=1098]

分析：

数学归纳法

f(1) = 18 + ka;

假设f(x) = 5 x ^13+13*x 5+k a*x 能被65整除

f(x+1) = 5 (x+1) ^13+13*(x+1) 5+k a*(x+1)

根据二项式定理展开 (a+b)^n = C(n,0) a ^n*b 0 + C(n,1) a ^(n-1)*b 1 + C(n,2) a ^(n-2)*b 2 + ... + C(n,n) a ^0*b n

f(x+1) = 5 * (x^13 + C(13,1) x^12 + C(13,2) x^11 + ... + C(13,13)) + 13 * (x^5 + C(5,1) x^4 + .. + C(5,5)) + k x*a + ka;

补充：组合数性质 C(n, m) (m < n) 如果n为质数 则C(n, m)能被n整除。

证明：

C(n, m) = n! / (m! * (n-m)!) = (n-m+1) * (n-m+2) * ... * n / m!

m = 1: C(n, m) = n; C(n, m) % n = 0;

1 < m < n: 因为C(n, m)为整数，n为质数，m!为合数，n / m! 不是整数，进而(n-m+1) * (n-m+2) * ... * (n-1) / m!必为整数，所以C(n, m)能被n整除。

证毕。

化简 : f(x+1) = 5 x^13 + 5 13 g(x) + 5 + 13 x^5 + 13 5 h(x) + 13 + k x a + ka;

= f(x) + 65 g(x) + 65 h(x) + 18 + ka;

只要证明 18 + ka 能被65整除。

又因为(a + b) mod m = (a mod m + b mod n) mod m

所以只要证明 ka 能被 47 整除。

代码

#include <iostream>

using namespace std;

int main()

{

    int k, a;

    while(cin >> k) {

        if(k % 65 == 0) {

            cout << "no" << endl;

            continue;

        }

        for(a=0; a<65; a++) {

            if(k*a % 65 == 47) {

                cout << a << endl;

                break;

            }

        }

        if(a == 65) {

            cout << "no" <<endl;

        }

    }

    return 0;

}