BZOJ 2742: [HEOI2012]Akai的数学作业

2742: [HEOI2012]Akai的数学作业

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 535  Solved: 226
[Submit][Status][Discuss]

Description

这里是广袤无垠的宇宙这里是一泻千里的银河

这里是独一无二的太阳系

这里是蔚蓝色的地球

这里，就是这里，是富饶的中国大陆！

这里是神奇的河北大地

这里是美丽的唐山

这里是神话般的唐山一中

这里是Akai曾经的教室

黑板上还留有当年Akai做过的数学作业，其实也并不是什么很困难的题目:

 

给出一个一元n次方程：

a0 + a1x + a    2   x2 +…+ anxn= 0

求此方程的所有有理数解。

 

Akai至今还深刻记得当年熬夜奋战求解的时光

他甚至还能记得浪费了多少草稿纸

但是却怎么也想不起来最后的答案是多少了

你能帮助他么？

Input

第一行一个整数n。第二行n+1个整数，分别代表a    0 到a n

Output

第一行输出一个整数t，表示有理数解的个数

接下来t行，每行表示一个解

解以分数的形式输出，要求分子和分母互质，且分母必须是正整数特殊的，如果这个解是一个整数，那么直接把这个数输出

等价的解只需要输出一次

所有解按照从小到大的顺序输出

Sample Input

3
-24 14 29 6

Sample Output

3
-4
-3/2
2/3

HINT

【数据范围】

对于30%的数据，n<=10

对于100%的数据，n <= 100，|a i| <= 2*10^7，an≠ 0

Source

[Submit][Status][Discuss]

好神的一道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 = 105;
const int mxm = 500005;
const lnt mod = 1000000007;

int n, s[mxn];

struct number
{
    int a, b, f;    // ans = a / b

    number(void) {};
    number(int x, int y, int g = 1)
        : a(x), b(y), f(g) {};

    void print(void)
    {
        if (f == -1)
            putchar('-');
        if (a % b)
            printf("%d/%d
", a, b);
        else
            printf("%d
", a / b);
    }
}ans[mxm]; int tot;

bool cmp(const number &A, const number &B)
{
    if (A.f == -1 && B.f == +1)
        return true;
    if (A.f == +1 && B.f == -1)
        return false;
    if (A.f == +1 && B.f == +1)
        return 1LL * A.a * B.b < 1LL * B.a * A.b;
    if (A.f == -1 && B.f == -1)
        return 1LL * A.a * B.b > 1LL * B.a * A.b;
}

void leadingZeros(void)
{
    int cnt = 0;

    while (!s[cnt])
        ++cnt;

    if (cnt)
    {
        n = n - cnt;
    
        for (int i = 0; i <= n; ++i)
            s[i] = s[i + cnt];
    
        ans[tot++] = number(0, 1);
    }
}

int divA[mxm], sizA;
int divB[mxm], sizB;

void divide(int x, int *div, int &siz)
{
    if (x < 0)x = -x;

    siz = 0;

    int t = int(sqrt(x));

    for (int i = 1; i <= t; ++i)
        if (x % i == 0)
        {
            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[0] = powB[0] = 1LL;

    for (int i = 1; i <= n; ++i)
    {
        powA[i] = (powA[i - 1] * a) % mod;
        powB[i] = (powB[i - 1] * b) % mod;
    }

    lnt sum = 0, tmp;

    for (int i = 0; i <= n; ++i)
    {
        tmp = s[i];
        tmp = (tmp * powA[i]) % mod;
        tmp = (tmp * powB[n - i]) % mod;

        if (i & 1)tmp = (tmp * f + mod) % mod;

        sum = (sum + tmp) % mod;
    }

    if (sum == 0)ans[tot++] = number(a, b, f);
}

signed main(void) 
{
    scanf("%d", &n);

    for (int i = 0; i <= n; ++i)
        scanf("%d", s + i);

    leadingZeros();

    divide(s[0], divA, sizA);
    divide(s[n], divB, sizB);

    for (int i = 0; i < sizA; ++i)
        for (int j = 0; j < sizB; ++j)
        {
            int a = divA[i];
            int b = divB[j];

            if (gcd(a, b) == 1)
            {
                check(a, b, +1);
                check(a, b, -1);
            }
        }

    std::sort(ans, ans + tot, cmp);

    printf("%d
", tot);

    for (int i = 0; i < tot; ++i)
        ans[i].print();
}

@Author: YouSiki