首页 > ACM题库 > HDU-杭电 > HDU 4569-Special equations-数论-[解题报告]HOJ
2015
07-25

HDU 4569-Special equations-数论-[解题报告]HOJ

Special equations

问题描述 :

  Let f(x) = anxn +…+ a1x +a0, in which ai (0 <= i <= n) are all known integers. We call f(x) 0 (mod m) congruence equation. If m is a composite, we can factor m into powers of primes and solve every such single equation after which we merge them using the Chinese Reminder Theorem. In this problem, you are asked to solve a much simpler version of such equations, with m to be prime’s square.

输入:

  The first line is the number of equations T, T<=50.
  Then comes T lines, each line starts with an integer deg (1<=deg<=4), meaning that f(x)’s degree is deg. Then follows deg integers, representing an to a0 (0 < abs(an) <= 100; abs(ai) <= 10000 when deg >= 3, otherwise abs(ai) <= 100000000, i<n). The last integer is prime pri (pri<=10000).
  Remember, your task is to solve f(x) 0 (mod pri*pri)

输出:

  The first line is the number of equations T, T<=50.
  Then comes T lines, each line starts with an integer deg (1<=deg<=4), meaning that f(x)’s degree is deg. Then follows deg integers, representing an to a0 (0 < abs(an) <= 100; abs(ai) <= 10000 when deg >= 3, otherwise abs(ai) <= 100000000, i<n). The last integer is prime pri (pri<=10000).
  Remember, your task is to solve f(x) 0 (mod pri*pri)

样例输入:

4
2 1 1 -5 7
1 5 -2995 9929
2 1 -96255532 8930 9811
4 14 5458 7754 4946 -2210 9601

样例输出:

Case #1: No solution!
Case #2: 599
Case #3: 96255626
Case #4: No solution!

题意:给你函数 f(x) = anxn +…+ a1x +a0
最多N就4位,输入任意一个x使f(x)%(prime*prime)=0。

这题枚举就可以,首先如果满足f(x)%(prime*prime)=0必须要满足f(x)%prime=0这个条件。

那么应该先找到一个x满足f(x)%prime=0,然后在(x-prime*prime)区间内x+=prime(保证f(x)%prime=0总成立),如果有f(x)%(prime*prime)=0那么就输出。

找出一个x在(0-prime)区间内找,找到后不断加prime,所以这样找在区间(1-prime*prime)内所有的x满足f(x)%prime=0都找出来了。

对于任意一个大于pri*pri的数n,我们都可以将其成写n=(pri*pri)*t+k的形式,其中t为整数,k<=pri*pri;那么f(pri*pri*t+k)的值就相当于在f(k)的值的基础上增加了pri*pri的倍数;所以若f(k)%pri*pri==0不成立,则f(pri*pri*t+k)%pri*pri==0也不会成立;因此若在1到pri*pri之间不能找到一个x使得f(x)%pri*pri==0成立,那么就不存在一个x使得f(x)%pri*pri==0成立

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[10];
long long getf(long long x,int n)
{
    long long sum=0;
    for(int i=0; i<n; i++)
        sum+=a[i],sum*=x;
    return sum+a[n];
}
void solve(int n,long long pri)
{
    long long i,j,mod=pri*pri;
    for(i=0; i<pri; i++)
        if(getf(i,n)%pri==0)
            for(j=i; j<mod; j+=pri)
                if(getf(j,n)%mod==0)
                {
                    printf("%I64d\n",j);
                    return;
                }
    puts("No solution!");
}
int main()
{
    int t,n,ca=0;
    long long pri;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n+1; i++)
            scanf("%I64d",&a[i]);
        scanf("%I64d",&pri);
        printf("Case #%d: ",++ca);
        solve(n,pri);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/prime7/article/details/9120007