首页 > ACM题库 > HDU-杭电 > HDU 4447-Yuanfang, What Do You Think?-模拟-[解题报告]HOJ
2015
07-16

HDU 4447-Yuanfang, What Do You Think?-模拟-[解题报告]HOJ

Yuanfang, What Do You Think?

问题描述 :

Factoring a polynomial is always a hard and important issue in mathematics teaching in middle schools. Teacher Liu loves teaching this issue very much, but his students are not good at it.
Yuanfang is the best student in Teacher Liu’s class. Every time when Teacher Liu comes up with a hard problem and it seems no student can solve it, Liu always says: "Yuanfang , what do you think?"。
This week, Teacher Liu began to teach how to factor a polynomial. On Monday, Teacher Liu said : "Let’s factor x2-1 … Yuanfang, what do you think?"
On Tuesday, Teacher Liu said : "Let’s factor x3-1 … Yuanfang, what do you think?"
On Wednesday, Teacher Liu said : "Let’s factor x4-1 … Yuanfang, what do you think?"
…..
On Friday, Yuanfang got crazy. She wanted to solve this problem permanently. So she came to you, the only programmer she knows, for help.
You should write a program to factor the polynomial xn-1. In other words, represent the polynomial xn-1 by a product of irreducible polynomials in which coefficients are all integers.

输入:

There are several test cases. Every case is an integer n in a line (n≤1100) meaning that you should factor the polynomial xn-1.
Input ends with n=0.

输出:

There are several test cases. Every case is an integer n in a line (n≤1100) meaning that you should factor the polynomial xn-1.
Input ends with n=0.

样例输入:

1
2
3
4
5
6
0

样例输出:

x-1
(x-1)(x+1)
(x-1)(x^2+x+1)
(x-1)(x+1)(x^2+1)
(x-1)(x^4+x^3+x^2+x+1)
(x-1)(x+1)(x^2-x+1)(x^2+x+1)

题目大意:

就是现在对于给定的多组数据, 对于每组的n (1 <= n <= 1100) 分解多项式 (x^n – 1)

例如 x^2 – 1 = (x-1)(x+1)

x^3 – 1 = (x-1)(x^2+x+1)

x^4 – 1 = (x-1)(x+1)(x^2+1)

输出顺序按照多项式从小到大输出,(多项式大小比较先比较长度, 然后高次项到低次项比较系数的绝对值, 如果绝对值相同则负的较小

大致思路:

这个题是看了官方的题解才知道怎么做的, 首先可以观察规律

用p[i]表示(x^i – 1)分解之后得到的多项式中其独有的一项

那么(x^i – 1)分解之后得到的是P(k1)P(k2)P(k3)…P(kx) * p[i]

其中k1, k2, k3…kx是i的所有约数

例如 p[1] = x – 1, p[2] = x + 1, p[3] = x^2 + x + 1, p[4] = (x^2 + 1), p[5] = x^4 + x^3 + x^2 + x + 1, p[6] = x^2 + x + 1

而x^6 – 1 = p[1]*p[2]*p[3]*p[6]…

所有的多项式(x^i – 1)都可以分解成这样的形式, 恰好是 i 的所有约数对应的这些独有的多项式的乘积

可以参考这篇论文 : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.3592&rep=rep1&type=pdf

那么知道上面这些之后就可以运处理所有的独有的多项式了(直接模拟多项式除法)

因为所有系数都是整数并且可以保证能整除, 所以除法很容易写

左后对于所有分解出来的式子按照题目给的大小进行排序即可, 复杂度O(n*n*logn)

代码如下:

Result  :  Accepted     Memory  :  6524 KB     Time  :  312 ms

/*
 * Author: Gatevin
 * Created Time:  2015/3/18 13:24:26
 * File Name: Kotori_Itsuka.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

#define maxn 1110
vector <int> v[maxn];

struct polynomial
{
    int coe[maxn];
    int len;
    polynomial()
    {
        memset(coe, 0, sizeof(coe));
        len = 1;
    }
    void output()
    {
        printf("(");
        for(int i = len - 1; i >= 0; i--)
        {
            if(coe[i] == 0) continue;
            if(i == 0)
            {
                if(coe[i] > 0) printf("+");
                printf("%d", coe[i]);
                continue;
            }
            if(coe[i] > 0 && i != len - 1) printf("+");
            if(coe[i] == -1) printf("-");
            if(abs(coe[i]) != 1) printf("%d", coe[i]);
            if(i > 1)
                printf("x^%d", i);
            else printf("x");
        }
        printf(")");
        return;
    }
    polynomial operator / (const polynomial pol);
};

polynomial polynomial :: operator / (const polynomial pol)
{
    polynomial ret;
    ret.len = len - pol.len + 1;
    for(int i = len - 1; i >= pol.len - 1; i--)
    {
        int tim = coe[i] / pol.coe[pol.len - 1];
        if(tim != 0)
        {
            for(int j = 0; j < pol.len; j++)
                coe[i - j] -= tim*pol.coe[pol.len - 1 - j];
            ret.coe[i - pol.len + 1] = tim;
        }
    }
    return ret;
}

polynomial p[maxn];

bool cmp(int i, int j)//return p[i] < p[j]
{
    if(p[i].len != p[j].len) return p[i].len < p[j].len;
    for(int k = p[i].len - 1; k >= 0; k--)
        if(p[i].coe[k] != p[j].coe[k])
        {
            if(abs(p[i].coe[k]) == abs(p[j].coe[k]))
                return p[i].coe[k] < 0;
            else return abs(p[i].coe[k]) < abs(p[j].coe[k]);
        }
    return false;
}

int main()
{
    p[1].coe[0] = -1;
    p[1].coe[1] = 1;
    p[1].len = 2;//p[i] = (x - 1)
    for(int i = 2; i <= 1100; i++)//计算p[2~1100]的特殊多项式
    {
        p[i].coe[0] = -1;
        p[i].coe[i] = 1;
        p[i].len = i + 1;
        p[i] = p[i]/p[1];
        v[i].push_back(1);
        for(int j = 2; j*j <= i; j++)
        {
            if(i % j == 0)
            {
                p[i] = p[i]/p[j];
                v[i].push_back(j);
                if(j*j != i) p[i] = p[i]/p[i / j], v[i].push_back(i / j);
            }
        }
        v[i].push_back(i);
    }
    int n;
    while(scanf("%d", &n), n)
    {
        if(n == 1)
        {
            printf("x-1\n");
            continue;
        }
        sort(v[n].begin(), v[n].end(), cmp);
        for(int i = 0, sz = v[n].size(); i < sz; i++)
            p[v[n][i]].output();
        printf("\n");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/gatevin/article/details/44410853