解题思路

这道题要求我们找出一个给定多项式的所有整数根。根据数学中的多项式理论，一个整系数多项式的整数根必须是常数项的因数。因此，我们可以通过以下步骤来解决这个问题：

1. 预处理质数：生成所有小于60000的质数，用于后续分解常数项的质因数。
2. 分解常数项：对于每个输入的多项式，分解其常数项的质因数，从而得到所有可能的因数。
3. 验证可能的根：使用多个模数进行哈希验证，检查每个可能的因数是否为多项式的根。
4. 多项式降阶：找到一个根后，使用综合除法将多项式降阶，继续寻找剩余的根。

题意分析

输入是一个多项式，其最高次项系数为1，其他系数为整数。我们需要找出该多项式的所有整数根，并按升序输出。特别注意，如果有重根，每个根都需要被列出。

标程

以下是完整的解题代码，包含详细注释：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int64 __int64  // 使用64位整数类型
using namespace std;

// 多个模数用于哈希验证，减少误判的可能性
int64 MOD[]={13251349,13251361,13251367,
             13251373,13251377,13251383};
             
int64 prime[60000],isprime[60000],cnt;  // 存储质数及其标记

// 预处理质数表（埃拉托斯特尼筛法）
void init()
{
    int64 i,j;
    cnt=0;
    for(i=2;i<60000;i++)
    {
        if(!isprime[i]) prime[++cnt]=i;  // 如果i是质数，加入质数表
        for(j=1;j<=cnt&&prime[j]*i<60000;j++)
        {
            isprime[prime[j]*i]=1;  // 标记合数
            if(i%prime[j]==0) break;  // 优化筛法
        }
    }
}

// 存储质因数及其指数的结构体
struct node
{
    int64 prime,num;
};

node a[100];  // 存储分解后的质因数
int64 n,aNum,factor[10000],factorNum;  // 多项式次数、因数相关变量
int64 coef[105];  // 存储多项式系数

// 计算绝对值
int64 ABS(int64 x)
{
    if(x<0) return -x;
    return x;
}

// 深度优先搜索生成所有可能的因数
void DFS(int64 x,int dep)
{
    int64 i;
    if(dep==aNum+1)
    {
        factor[factorNum++]=x;  // 生成一个因数
    }
    else
    {
        for(i=0;i<=a[dep].num;i++)
        {
            DFS(x,dep+1);
            x=x*a[dep].prime;  // 累乘当前质因数
        }
    }
}

// 分解质因数并生成所有可能的因数
void cal(int64 p)
{
    aNum=0;
    int64 i;
    // 分解质因数
    for(i=1;i<=cnt;i++) if(p%prime[i]==0)
    {
        aNum++;
        a[aNum].prime=prime[i];
        a[aNum].num=0;
        while(p%prime[i]==0)
        {
            a[aNum].num++;
            p/=prime[i];
        }
    }
    if(p>1)  // 处理剩余的质因数
    {
        aNum++;
        a[aNum].prime=p;
        a[aNum].num=1;
    }
    factorNum=0;
    DFS(1,1);  // 生成所有因数
}

// 使用多个模数验证是否为根
int OK(int64 a)
{
    int64 r,b,i,j;
    for(i=0;i<6;i++)
    {
        r=0;
        b=a%MOD[i];
        // 霍纳法则计算多项式在模MOD[i]下的值
        for(j=n;j>=0;j--) r=(r*b+coef[j])%MOD[i];
        if(r) return 0;  // 如果不为0，则不是根
    }
    return 1;  // 所有模数下都为0，大概率是根
}

int64 ans[10005],ansNum;  // 存储找到的根及其数量

int main()
{
    init();  // 预处理质数表
    while(scanf("%d",&n)!=-1)  // 处理多个测试用例
    {
        int64 i,j,k,t,r,u;
        // 读取多项式系数（注意输入顺序与存储顺序的转换）
        for(i=n-1;i>=0;i--) scanf("%I64d",&coef[i]);
        coef[n]=1;  // 最高次项系数为1
        ansNum=0;
        k=0;
        factorNum=0;
        
        // 迭代寻找所有根
        while(n)
        {
            if(coef[0]==0)  // 如果常数项为0，说明x=0是一个根
            {
                ans[ansNum++]=0;
                // 多项式降阶（去掉x的因子）
                for(i=0;i<n;i++) coef[i]=coef[i+1];
                n--;
            }
            else
            {
                if(!factorNum) cal(ABS(coef[0]));  // 分解常数项的质因数
                t=0;
                // 检查每个可能的因数及其相反数
                for(i=k;i<factorNum;i++) if(coef[0]%factor[i]==0)
                {
                    if(OK(factor[i]))
                    {
                        t=factor[i];
                        k=i;
                        break;
                    }
                    if(OK(-factor[i]))
                    {
                        t=-factor[i];
                        k=i;
                        break;
                    }
                }
                if(!t) break;  // 没有找到更多根，退出循环
                ans[ansNum++]=t;
                
                // 综合除法：用(x-t)除多项式，得到降阶后的多项式
                r=0;
                for(i=n;i>=0;i--)
                {
                    u=r*t+coef[i];
                    coef[i]=r;
                    r=u;
                }
                n--;
            }
        }
        sort(ans,ans+ansNum);  // 按升序排序
        printf("%I64d\n",ansNum);  // 输出根的数量
        for(i=0;i<ansNum;i++) printf("%I64d\n",ans[i]);  // 输出每个根
    }
    return 0;
}

算法解释

1. 预处理质数表：使用埃拉托斯特尼筛法生成所有小于60000的质数，用于后续分解常数项的质因数。

2. 分解质因数：对于给定的常数项，分解其质因数并生成所有可能的因数（包括正负因数）。

3. 根的验证：使用多个模数对每个可能的因数进行验证，确保在多个模数下多项式的值都为0，从而减少误判的可能性。

4. 多项式降阶：找到一个根后，使用综合除法将多项式除以(x - root)，得到降阶后的多项式，继续寻找剩余的根。

这种方法充分利用了数学中的多项式理论和哈希验证技术，高效地找到了所有整数根，同时保证了结果的正确性。