质多项式

给定多项式f(x)＝a_nxⁿ＋a_n-1x^n-1+…+a₀x⁰，如果a_n<>0，我们称f(x)是一个n次多项式。

类似自然数里的“质数”的概念，也可以给出“质多项式”的概念。给定多项式f(x)，如果找不到次数至少为1的多项式g(x)和h(x)满足f(x)=g(x)＋h(x)，我们称f(x)是质多项式。

为了简化起见，我们规定多项式各项的系数只能取两个数：0或1。并且重新定义在{0，1}上的加法和乘法：

0＋0＝0，0＋1＝1，1＋0＝1，1＋1＝0

0×0＝0，0×1＝0，1×0＝0，0×0＝0

下面给出多项式相乘的例子：

(x₂＋x₁)×（x₁＋1）＝x₃＋x₂＋x₂＋x₁＝x₃＋x₁

                                                                                                                      ^.

在这个问题里，你需要写一个程序，对给定的正整数k，求出次数为k的质多项式的。

Simple input	Output for the input
1 2 5 13 0	X X^2+X+1 X^5+X^2+1 X^13+X^4+X^3+X^1+1

 

解：

观察题目可知这里的的加法运算XOR，其逆运算减法运算也是异或运算XOR。

乘法运算是与运算AND。

于是解题时可以按照穷举法逐个遍历，直到找到解为止。

还有一点需要注意的是K次质多项式必含有X^K和1项。

 

代码：

#include
#include
#include
#include
using namespace std;
vector bin(31);   //存放二进制位掩码的
//返回二进制表示中最高位的1的位置,其实就是多项式次数
inline int weight(int data)
{
    int i;
    for(i=30;i>=0;i--)
    if(bin[i]<=data)
        break;
    return i;
}
//返回a的二进制表示的多项式能否整除b的二进制形式表示的多项式, 我们不求商,只看余数是否为0 ，能否除尽
inline bool divide(int a,int b)
{
    int wa,wb;
    wa=weight(a);//多项式a的次数,其实就是他从高位向低位方向的第一个1的位置，即下标
    wb=weight(b);//多项式b的次数
    b=b<<(wa-wb);//b乘以（a除以b的商）,显然是偷师一般多项式的除法
    while(a!=b&&wa>=wb) //还没到除法的结束标志,即相除余数为0即a=b(除尽)或余数不为0即wa    {
        a=a^b;    //按定义知  a-b=a^b ,是自定义减法,非正常减法,a始终是余数
        while(bin[wa]>a)  //a-b必消去至少一个高位,则应商0,并向后对齐
        {
            --wa;
            b=b>>1;//方便对齐相减而已,本来为了减除数一开始就作了左移的
        }
        //至此已再一次对齐了可以相减了
    }
    return wa>=wb?true:false;
}
void output(int data)
{
    for(int i=30;i>0;i--)
        if(data&bin[i])    //i次幂系数不为0
        printf("x^%d+",i);
    printf("1 ");        //质多项式一定含1这一项,否则至少含有x这个因式，就枉称质多项式了
}
int main()
{
    bin[0]=1;
    for(int i=1;i<=30;i++)
    {
        bin[i]=bin[i-1]*2; //二进制mask数组,以空间换时间
    }
    int k,flag,i,now;
    //以2为增量穷举搜索各阶多项式
    while(1)
    {
        scanf("%d",&k);   //输入一个数, 表示要找的多项式的次数,当然需要构造这种次数的多项式
        cout<<"you input "<        if(k==0)    return 0;
       
        now=bin[k]-1;//以x^k为第一个多项式,开始查找质多项式
        do{
            if(now>=bin[k+1])  //超过x^(k+1)了，因为我们要找的是k次多项式,不是k+1次
            {
                puts("error");
                break;
            }
            cout<<"pj  "<            flag = false;         //是质多项式
            now += 2;              //增量为2,这样才能保证一定含有1,构造次数为k的多项式,不会大于x^(k+1)
//构造次数小于k的多项式即找多项式因子,当然从因子x即2开始,直到x^[(k+1)/2)]
//为什么是(k+1)/2+1呢?原因是我们找的次数为k的多项式的因子多项式即k+1个二进制位,基因子总是成对如现的,子因式最大为now的平方根因式，即次数为(k+1)/2的
//这样k/2次的多项式的二进表示最多为11....111,有(k+1)/2个(因为1是0次的),作为掩码就应该是2^[(k+1)/2+1]-1,
//也可以写为 <2^[(k+1)/2+1],这就是bin[(k+1)/2+1]的内容,
            for(i=2;i            {
                if(divide(now,i)==true)  //now可以整除i
                {
                    flag = true;
                    break;    //不是质多项式
                }
            }
        }while(flag);
        output(now);
    };
}