首页 > 代码库 > HDU_1098 Ignatius's puzzle[规律题]

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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<string>
#include<map>
#include<utility>
#include<queue>
#include<stack>
#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;
}





HDU_1098 Ignatius's puzzle[规律题]