hdu4589 Special equations(數論)

Special equations
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 206    Accepted Submission(s): 108
Special Judge

Problem Description
　　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.
 

Input
　　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)
 

Output
　　For each equation f(x) 0 (mod pri*pri), first output the case number, then output anyone of x if there are many x fitting the equation, else output "No solution!"
 

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

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

Source
2013 ACM-ICPC長沙賽區全國邀請賽——題目重現
 
題解：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!，這裡只需要枚舉到pri*pri，這個證法和前面的一樣

#include<stdio.h>   
  
int a[6],pri,n;  
  
__int64 getf(int x,int i)  
{  
    int j;  
    __int64 sum=0;  
    for(j=0;j<i;j++)  
    {  
        sum=(sum+a[j])*x;  
    }  
    return sum+a[j];  
}  
  
void solve()  
{  
    int i,j,k;  
    int pri2=pri*pri;  
    for(i=0;i<pri;i++)  
    {  
        if((getf(i,n))%pri==0)  
        {  
            for(j=i;j<pri2;j+=pri)  
            {  
                if(getf(j,n)%pri2==0)  
                {  
                    printf("%d\n",j);  
                    return ;  
                }  
            }  
        }  
    }  
    printf("No solution!\n");  
}  
int main()  
{  
    int i,j,k,t,no;  
    __int64 temp;  
    scanf("%d",&t);  
    for(k=1;k<=t;k++)  
    {  
        scanf("%d",&n);  
        for(i=0;i<=n;i++)  
        {  
            scanf("%d",&a[i]);  
        }  
        scanf("%d",&pri);  
        printf("Case #%d: ",k);  
        solve();  
    }  
    return 0;  
}  

#include<stdio.h>

int a[6],pri,n;

__int64 getf(int x,int i)
{
	int j;
	__int64 sum=0;
	for(j=0;j<i;j++)
	{
		sum=(sum+a[j])*x;
	}
	return sum+a[j];
}

void solve()
{
	int i,j,k;
	int pri2=pri*pri;
	for(i=0;i<pri;i++)
	{
		if((getf(i,n))%pri==0)
		{
			for(j=i;j<pri2;j+=pri)
			{
				if(getf(j,n)%pri2==0)
				{
					printf("%d\n",j);
					return ;
				}
			}
		}
	}
	printf("No solution!\n");
}
int main()
{
	int i,j,k,t,no;
	__int64 temp;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&n);
		for(i=0;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		scanf("%d",&pri);
		printf("Case #%d: ",k);
		solve();
	}
	return 0;
}