hdu4569 求解f(x)%(p*p)=0

http://acm.hdu.edu.cn/showproblem.php?pid=4569

首先如果f(x)%(p*p)=0，则必有f(x)%p=0，因此解x必然在满足f(x)%p=0的集合中。

接着注意到p为质数，f(x)为多项式，那么满足f(x)%p=0的集合在p的剩余系中必然很少，而由于f(x)为多项式，那么根据同余模定理，必然有f(x+k*p*p)=f(x) (mod p*p)。因此找到满足f(x)%p=0的集合x(x在p的剩余系中)，然后枚举k即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<math.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;

int n;
ll a[maxn],p;

ll qpow(ll n,ll k,ll p)
{
    ll res=1;
    while(k){
        if(k&1) res=(res*n)%p;
        n=(n*n)%p;
        k>>=1;
    }
    return res;
}

ll f(ll x,ll p)
{
    ll res=0;
    REP(i,0,n){
        res=(res+a[i]*qpow(x,i,p))%p;
    }
    return res;
}

int main()
{
    freopen("in.txt","r",stdin);
    int T;cin>>T;int casen=1;
    while(T--){
        scanf("%d",&n);
        for(int i=n;i>=0;i--) scanf("%I64d",&a[i]);
        scanf("%I64d",&p);
        REP(i,0,n){
            while(a[i]<0) a[i]+=p*p*100000;
            a[i]%=p*p;
        }
        bool flag=0;
        ll ans=-1;
        REP(x,0,p-1){
            if(f(x,p)==0){
                for(ll y=x;y<p*p;y+=p){
                    if(f(y,p*p)==0){
                        ans=y;flag=1;
                    }
                    if(flag) break;
                }
            }
            if(flag) break;
        }
        printf("Case #%d: ",casen++);
        if(flag) printf("%I64d
",ans);
        else puts("No solution!");
    }
    return 0;
}

唉，我怎么那么笨，连这都没看出来。。

总结，如果对于f(x)=y(mod p) ，如果f(x)为多项式，那么就应该善于用同余模定理，如果找解的话，可以考虑枚举，但要注意枚举的范围，不要去枚举那些明显不在解集中的数。