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顯示時鍾可以調節時分秒（加減）