HDU 4569 Special equations (数学题)

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4569

题意：给你一个最高幂为4的一元多项式，让你求出一个x使其结果模p*p为0.

题解：f(x)%(p*p)=0那么一定有f(x)%p=0，f(x)%p=0那么一定有f(x+p)%p=0。

所以我们可以开始从0到p枚举x，当f(x)%p=0，然后再从x到p*p枚举，不过每次都是+p，找到了输出即可，没有的话No solution!

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef __int64 LL;

const int N=1;

const LL mod=1000000007LL;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

LL xi[6],p2,p;

int n;

LL ff(LL x,LL k)

{

    LL sum=0,ans=1;

    for(int i=0;i<=n;i++)

    {

        sum=(sum+xi[i]*ans)%k;

        ans*=x;

    }

    return (sum+k)%k;

}

void xiaohao()

{

    LL i,x,x2;

    for(x=0;x<p;x++)

    {

        LL t=ff(x,p);

        if(t%p==0)

        {

            for(x2=x;x2<p2;x2+=p)

            {

                LL t2=ff(x2,p2);

                if(t2%p2==0)

                {

                    printf("%I64d\n",x2);

                    return ;

                }

            }

        }

    }

    printf("No solution!\n");

}

int main()

{

    int i,j,T,ca=0;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(i=n;i>=0;i--)

            scanf("%I64d",&xi[i]);

        scanf("%I64d",&p);

        p2=p*p;

        printf("Case #%d: ",++ca);

        xiaohao();

    }

    return 0;

}

巴特西

HDU 4569 Special equations (数学题)

最新文章

热门文章