本文主要是介绍HDU 4569 Special equations 枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
本题的意思：已知f(x) = a nx n+...+ a 1x +a 0 ，整数m,m一个素数的平方。求出x使f(x) mod (m)＝0;
给出a nto a 0，(0 < abs(a n)<= 100; abs(a i)<= 10000 when deg >= 3, otherwise abs(a i) <= 100000000, i<n) ，prime pri (pri<=10000)
解题思路：直接枚举(1-1e8)的话会超时
因为m＝pri*pri,且 m|f(x)，那么pri| f(x)，所以我们从0-pre-1枚举x0是否符合pri| f(x0) 如果没有直接输出Nosolution!
如果有那么我们可以枚举t x=x0+t*pri; 因为我们要保证pre| f(x) 所以 xmod(pri)=x0 如果有t符合pri*pri| f(x) 输出x 否则输出No solution!
代码：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll quickmod(ll a,ll b,ll mod){ll ans=1;while (b) {if (b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
ll a[5];
bool check(ll t,ll mod,ll a0,ll x){ll ans=0;for (ll i=t;i; --i) {ans=(ans+(a[i]%mod)*quickmod(x,i,mod)%mod)%mod;}return (ans+a0)%mod==0;
}int main(int argc, const char * argv[]) {ll t,n,a0,mod,x;cin>>n;int cnt=0;while (n--) {cin>>t;bool ok=false;for (ll i=t; i>0; --i)cin>>a[i];cin>>a0>>mod;x=mod;for (ll i=0;i<mod;++i) {if (check(t,mod,a0,i)) {ok=true;x=i;break;}}cout<<"Case #"<<++cnt<<": ";if (!ok) {puts("No solution!");continue;}ok=false;for (ll i=x;i<=mod*mod;i+=mod) {if (check(t,mod*mod,a0,i)){cout<<i<<endl;ok=true;break;}}if (!ok)puts("No solution!");}return 0;
}这篇关于HDU 4569 Special equations 枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
