关于HDOJ 1098题(Ignatius's puzzle) 的理解(C/C++)

题目描述

                       Ignatius’s puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12827 Accepted Submission(s): 9025

Problem Description
    Ignatius is poor at math,he falls across a puzzle problem,so he has no choice but to appeal to Eddy. this problem describes that:f(x)=5x^13+13x^5+kax,input a nonegative integer k(k<10000),to find the minimal nonegative integer a,make the arbitrary integer x ,65|f(x)if
no exists that a,then print “no”.

Input
    The input contains several test cases. Each test case consists of a nonegative integer k, More details in the Sample Input.

Output
    The output contains a string “no”,if you can’t find a,or you should output a line contains the a.More details in the Sample Output.

Sample Input
11
100
9999

Sample Output
22
no
43

Author
    eddy

原题链接

More info:Question

数学归纳法（第一数学归纳法）

1）当n=初始值时（一般为1或者0或者2之类的）,显然成立.

2）假设当n=k时（把式中n换成k,写出来）成立,

则当n=k+1时,（这步比较困难,化简步骤往往繁琐,考试时可以直接写结果)该式也成立.

由（1）（2）得,原命题对任意正整数均成立

排列组合（高中内容，快忘了……）

排列A_n ^m = n×（n-1）.（n-m+1）=n!/（n-m）!(n为下标,m为上标,以下同)

组合C_n ^m = P(n,m)/P(m,m) =n!/(m!（n-m）!)；

例如A₄ ² = 4!/2!=4 * 3=12

C₄ ² = 4!/(2! * 2!)=4 * 3/(2 * 1)=6

Accepted代码

代码很简单：

但是要先了解如果k * a+18能整除65，那么f（x）就能整除65

#include<iostream>
using namespace std;
int k, a;
int main() {
    while (cin >> k) {
        a = -1;
        for (int i = 0; i < 66; i++) {
            if ((18 + k * i )% 65 == 0) {
                a = i;
                break;
            }
        }
        if (a != -1) cout << a << endl;
        else cout << "no" << endl;
    }
    return 0;
}

数学归纳法应用:

证明：当k * a+18能整除65时，f（x）能整除65

假设f（x）能整除65

f（x）= 5 * x ¹³> + 13 * x ⁵> + k * a * x

则

f（x+1）= 5 * (x+1) ¹³+ 13 * (x+1) ⁵ + k * a * (x+1)

按二项式展开:

f（x+1）=5 （C₁₃ ¹³ * X¹³ +C₁₃ ¹² * X ¹² +C₁₃ ¹¹ * X ¹¹ +……+C₁₃ ⁰ * x ⁰）+ 13 (C₅ ⁵ * X ⁵ +C₅ ⁴ * X ⁴ +…+ C ₅ ⁰ * x⁰)+k * a * (x+1)

=f(x)+13 （C₁₃¹² * X¹²+C₁₃¹¹ X¹¹+……+C₁₃⁰ x⁰)+5(C₅⁴ * X⁴+…+C₅⁰ * x⁰)+k * a

=f(x)+5（X⁵+C₅⁴ * X⁴+…+C₅¹ * x¹）+13(C₁₃¹² * X¹²+C₁₃¹¹ * X¹¹+……+C₁₃¹ * x¹）+ k * a+18

(p.s: 18=C₁₃¹+C₅¹)

f(x）/65能整除，而多项式5（X⁵+C₅⁴ * X⁴+…+C₅¹ * x¹）+13(C₁₃¹² * X¹²+C₁₃¹¹ * X¹¹+……+C₁₃¹ * x¹） 也能整除65，

所以当k * a+18能整除65时即f(x+1)能整除65

综上所述，当k * a+18能整除65时，f（x）能整除65

参考博客

非常感谢qq_38294039的博文