591      阿里云  技术社区[云栖]

HDU 4569 长沙E题 枚举

题意：给你函数 f(x) = a_nxⁿ +...+ a₁x +a_{0 最多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;
}

最后更新：2017-04-03 18:52:14

  上一篇： 数据结构开场白

  下一篇： 1602显示时钟可以调节时分秒（加减）