您的位置: 首页  >  IT文章  >  解方程(hash，秦九韶算法)

解方程(hash，秦九韶算法)

分类: IT文章 • 2022-05-17 10:27:54

题目描述

已知多项式方程：

a0+a1x+a2x2+⋯+anxn=0

求这个方程在 [1,m]内的整数解（n 和 m 均为正整数）。

输入输出格式

输入格式：

共 n+2 行。

第一行包含 2个整数 n,m，每两个整数之间用一个空格隔开。

接下来的 n+1n+1n+1 行每行包含一个整数，依次为 a0,a1,a2…an

输出格式：

第一行输出方程在 [1,m] 内的整数解的个数。

接下来每行一个整数，按照从小到大的顺序依次输出方程在 [1,m]内的一个整数解。

思路：

有一个奇妙的东西叫秦九韶算法

（不知道的请左转百度）

然后我们看到a都很大

于是我们想到了hash

将 a hash掉

之后验证时取膜即可

代码：

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
#define p1 19260817
#define p2 23333
using namespace std;
char ai[10005];
long long a1[105],a2[105];
int ans[1000005],n,m,cnt;
inline void c1(int wz,int len)
{
    int pd=1;
    int fi=0;
    if(ai[0]=='-')
    {
        pd=-1;
        fi=1;
    }
    long long ans=ai[fi]-'0';
    for(rii=fi+1;i<=len-1;i++)
    {
        ans*=10;
        ans+=ai[i]-'0';
        ans%=p1;
    }
    a1[wz]=ans*pd;
}
inline void c2(int wz,int len)
{
    int pd=1;
    int fi=0;
    if(ai[0]=='-')
    {
        pd=-1;
        fi=1;
    }
    long long ans=ai[fi]-'0';
    for(rii=fi+1;i<=len-1;i++)
    {
        ans*=10;
        ans+=ai[i]-'0';
        ans%=p2;
    }
    a2[wz]=ans*pd;;
}
inline bool check(int v)
{
    long long ans=a1[n];
    for(rii=n;i>=1;i--)
    {
        ans*=v;
        ans%=p1;
        ans+=a1[i-1];
        ans%=p1;
    }
    if(ans!=0)
    {
        return 0;
    }
    ans=a2[n];
    for(rii=n;i>=1;i--)
    {
        ans*=v;
        ans%=p2;
        ans+=a2[i-1];
        ans%=p2;
    }
    if(ans!=0)
    {
        return 0;
    }
    return 1;
}
inline void sr()
{
    int wz=0;
    char l=getchar();
    while(l!=10)
    {
        ai[wz]=l;
        l=getchar();
        wz++;
    }
}
int main()
{
    scanf("%d%d
",&n,&m);
    for(rii=0;i<=n;i++)
    {
        memset(ai,0,sizeof(ai));
//        scanf("%s",ai);
        sr();
        int ltt=strlen(ai);
        c1(i,ltt);
        c2(i,ltt);
    }
//    for(rii=0;i<=n;i++)
//    {
//        cout<<a2[i]<<" ";
//    }
    for(rii=1;i<=m;i++)
    {
        if(check(i)==1)
        {
            cnt++;
            ans[cnt]=i;
        }
    }
    cout<<cnt<<endl;
    for(rii=1;i<=cnt;i++)
    {
        printf("%d
",ans[i]);
    }
}

相关推荐