Codeforces 902 D.GCD of Polynomials 数学,搜索答案

时间：2022-06-09 16:08:58

题意

给出n(1–150).
输出两个多项式A,B从常数到最高次的系数,使得对两个多项式求gcd时,恰好经过n步得到结果.
多项式的gcd一步是指(A(x),B(x))变成(B,A mod B)的过程,且当A mod B为0时,视为得到结果B.
A mod B为多项式求余,参见 long division.
要求两个多项式的所有系数都是1,0,-1.前导系数(最高次项系数)为1,度数(最高次)不超过n,第一个多项式的度数大于第二个.

样例输入
1
样例输出
1
0 1
0
1
表示x和1,进行一次得到结果.(x,1)–>(1,0)

样例输入
2
样例输出
2
-1 0 1
1
0 1
表示 x^2-1和x,进行两次得到结果(x^2-1,x)–>(x,-1)–>(-1,0)

解法

题目很长,比较难以理解.
数学题先推结论.
显然输入为n时,输出总是度数为n和n-1的两个多项式.
自然想到是否存在一个多项式序列an,使得ai和a(i+1)的gcd运算需要i步.
令a1=1 , a2=x , a3可以为x^2±1
多次实验发现a(i+2)=a(i+1)*x±ai可以递推.
如果150项内均有满足条件的式子,那么显然问题得解.

验证用代码

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std;
int save[160][160], tmp[160];
//第一维deg 最高次,从0开始
//第二维bit 每一位的系数,[0,deg]
int main(void)
{
    save[0][0] = 1; //常数1
    save[1][1] = 1; //x+0
int outoutflag=1;
for(int deg = 2; deg < 160; deg++)
    {
for(int bit = 1; bit <= deg; bit++)
            save[deg][bit] = save[deg - 1][bit - 1];

int outflag = 0;
for(int k = -1; k <= 1; k += 2)
        {
int flag = 1;
for(int bit = 0; bit <= deg - 2; bit++)
            {
                tmp[bit] = save[deg][bit] + save[deg - 2][bit] * k;
if(tmp[bit] <= -2 || tmp[bit] >= 2)
                {
                    flag = 0;
break;
                }
            }
if(flag == 1)
            {
for(int bit = 0; bit <= deg - 2; bit++)
                    save[deg][bit] = tmp[bit];
                outflag = 1;
break;
            }
        }
if(outflag == 0)
        {
printf("unsuccesful in %d\n", deg);
            outoutflag=0;
break;
        }
    }
if(outoutflag==1)
printf("succesful!" );
return 0;
}

使用的是非常simple的搜索验证,甚至没有回溯.
验证成功,直接按验证的结果打表输出即可.

代码

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std;
int save[160][160], tmp[160];
//第一维deg 最高次,从0开始
//第二维bit 每一位的系数,[0,deg]
int main(void)
{
    save[0][0] = 1; //常数1
    save[1][1] = 1; //x+0
for(int deg = 2; deg < 160; deg++)
    {
for(int bit = 1; bit <= deg; bit++)
            save[deg][bit] = save[deg - 1][bit - 1];

int outflag = 0;
for(int k = -1; k <= 1; k += 2)
        {
int flag = 1;
for(int bit = 0; bit <= deg - 2; bit++)
            {
                tmp[bit] = save[deg][bit] + save[deg - 2][bit] * k;
if(tmp[bit] <= -2 || tmp[bit] >= 2)
                {
                    flag = 0;
break;
                }
            }
if(flag == 1)
            {
for(int bit = 0; bit <= deg - 2; bit++)
                    save[deg][bit] = tmp[bit];
                outflag = 1;
break;
            }
        }
if(outflag == 0)
        {
printf("unsuccesful in %d\n", deg);
break;
        }
    }

int n;
scanf("%d", &n);
printf("%d\n", n );
for(int bit = 0; bit <= n; bit++)
printf("%d ", save[n][bit] );
printf("\n%d\n", n - 1 );
for(int bit = 0; bit <= n - 1; bit++)
printf("%d ", save[n - 1][bit] );
return 0;
}

注意

程序中多次用到了一种控制流程如下

int flag=1;
for(/*something*/)
{
/*something*/
if(/*something*/)
    {
        flag=0;
break;
    }
}
if(flag)
/*something*/
else
/*something*/

for循环部分实际为检验flag是否为1,同时可能有其它副作用.
在验证程序中,这样的部分嵌套了3次,对于编写代码带来很大的困难.
可以考虑使用函数等方式解决.

要敢于搜索和打表答案!积极写程序,不要用手搜!

标签：

相关文章