2742: [HEOI2012]Akai的数学作业
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 535 Solved: 226
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
-24 14 29 6
Sample Output
-4
-3/2
2/3
HINT
【数据范围】
对于30%的数据，n<=10
对于100%的数据，n <= 100，|a i| <= 2*10^7，an≠ 0
Source
好神的一道HEOI题。
据LH讲，有个定理叫做多项式高斯引理什么的，大概就是讲，复数域下的一个关于$x$的$n$次多项式$f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+...+a_{n}x^{n}$一定可以分解成$n$个含$x$的一次多项式相乘，即$f(x)$一定存在一种形如$f(x)=\prod{(b_{i}x+c_{i})}$的表示，其中每个式子都会产生一个复数域下的根（当然，这些根有可能重复）。这道题叫我们只用考虑有理数根，所以可以把式子改写为$f(x)=g(x)*\prod{(b_{i}x+c_{i})}$的样子，其中g(x)是一个关于$x$的多项式，包含了所有的非有理数根，剩下的部分就表示了所有的有理数根。发现每个有理数根都能表示成$x_{i}=\frac{c_{i}}{b_{i}}$，然后不难发现$f(x)=\sum_{i=0}^{n}{a_{i}x^{i}}$中的$a_{0}$包含了所有的$c_{i}$，而$a_{n}$包含了有所的$b_{i}$，所以对于所有的合法有理数根$x_{i}=\frac{c_{i}}{b_{i}}$，$c_{i}$一定是$a_{0}$的约数，$b_{i}$一定是$a_{n}$的约数。所以可以先处理出$a_{0}$和$a_{n}$的所有约数，然后暴力枚举$b_{i}$和$c_{i}$，$O(N)$check是否合法即可。check的方式是，对于$x=\frac{p}{q}$，$f(x)=\sum_{i=0}^{n}{a_{i}p^{i}q^{n-i}}$，在模意义下检查是否为$0$即可。
#include <bits/stdc++.h> template <class T>
T gcd(T a, T b)
{
return b ? gcd(b, a % b) : a;
} typedef long long lnt; const int mxn = ;
const int mxm = ;
const lnt mod = ; int n, s[mxn]; struct number
{
int a, b, f; // ans = a / b number(void) {};
number(int x, int y, int g = )
: a(x), b(y), f(g) {}; void print(void)
{
if (f == -)
putchar('-');
if (a % b)
printf("%d/%d\n", a, b);
else
printf("%d\n", a / b);
}
}ans[mxm]; int tot; bool cmp(const number &A, const number &B)
{
if (A.f == - && B.f == +)
return true;
if (A.f == + && B.f == -)
return false;
if (A.f == + && B.f == +)
return 1LL * A.a * B.b < 1LL * B.a * A.b;
if (A.f == - && B.f == -)
return 1LL * A.a * B.b > 1LL * B.a * A.b;
} void leadingZeros(void)
{
int cnt = ; while (!s[cnt])
++cnt; if (cnt)
{
n = n - cnt; for (int i = ; i <= n; ++i)
s[i] = s[i + cnt]; ans[tot++] = number(, );
}
} int divA[mxm], sizA;
int divB[mxm], sizB; void divide(int x, int *div, int &siz)
{
if (x < )x = -x; siz = ; int t = int(sqrt(x)); for (int i = ; i <= t; ++i)
if (x % i == )
{
div[siz++] = i;
div[siz++] = x / i;
} if (t * t == x)--siz;
} int powA[mxn];
int powB[mxn]; void check(lnt a, lnt b, lnt f)
{
powA[] = powB[] = 1LL; for (int i = ; i <= n; ++i)
{
powA[i] = (powA[i - ] * a) % mod;
powB[i] = (powB[i - ] * b) % mod;
} lnt sum = , tmp; for (int i = ; i <= n; ++i)
{
tmp = s[i];
tmp = (tmp * powA[i]) % mod;
tmp = (tmp * powB[n - i]) % mod; if (i & )tmp = (tmp * f + mod) % mod; sum = (sum + tmp) % mod;
} if (sum == )ans[tot++] = number(a, b, f);
} signed main(void)
{
scanf("%d", &n); for (int i = ; i <= n; ++i)
scanf("%d", s + i); leadingZeros(); divide(s[], divA, sizA);
divide(s[n], divB, sizB); for (int i = ; i < sizA; ++i)
for (int j = ; j < sizB; ++j)
{
int a = divA[i];
int b = divB[j]; if (gcd(a, b) == )
{
check(a, b, +);
check(a, b, -);
}
} std::sort(ans, ans + tot, cmp); printf("%d\n", tot); for (int i = ; i < tot; ++i)
ans[i].print();
}
@Author: YouSiki