程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU_1098 Ignatius&#39;s puzzle[規律題]

HDU_1098 Ignatius&#39;s puzzle[規律題]

編輯：C++入門知識

HDU_1098 Ignatius's puzzle[規律題]

Ignatius's puzzle

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)=5*x^13+13*x^5+k*a*x,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

題意：f(x)=5*x^13+13*x^5+k*a*x,找出最小的a，使得對於給定的k，任意x下f（x）能被65整除。

思路：打表找規律。

你會發現，（5*x^13+13*x^5）%65每65個x成循環。要使結果成立（k*a*x）%65，也得每65個循環，且a的值在0-64之間，所以就有如下代碼-> _ ->

代碼：

/************************************************
* Author: Ac_sorry
* File:
* Create Date:
* Motto: One heart One life
* CSDN: http://blog.csdn.net/code_or_code
*************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define seed_ 131
#define eps 1e-8
#define mem(a,b) memset(a,b,sizeof a)
#define w(i) T[i].w
#define ls(i) T[i].ls
#define rs(i) T[i].rs
using namespace std;
typedef long long LL;

const int N=100010;

int a[100];

int main()
{
    //int T;scanf("%d",&T);
    //int AC=0;
    for(int x=1;x<=65;x++)
        a[x]=(5*x%65*x*x%65*x*x%65*x*x%65*x*x%65*x*x%65*x*x%65+13*x%65*x*x%65*x*x%65)%65;
    int k;
    while(scanf("%d",&k)==1)
    {
        int ok,ans;
        for(int aa=0;aa<65;aa++)
        {
            ok=1;
            for(int i=1;i<=65;i++)
            {
                if((a[i]+k*i%65*aa%65)%65!=0)
                {
                    ok=0;
                    break;
                }
            }
            if(ok)
            {
                ans=aa;
                break;
            }
        }
        if(ok)
            printf("%d\n",ans);
        else
            printf("no\n");
    }
    return 0;
}