P2312 解方程 题解(作业)

    科技2024-07-01  65

    题面

    题目描述

    现有一个一元高阶方程:

    a 0 + a 1 ∗ x + a 2 ∗ x 2 + . . . + a n ∗ x n = 0 a0+a1*x+a2*x^2+...+an*x^n=0 a0+a1x+a2x2+...+anxn=0

    现给出数字 m m m,求出此方程在 [ 1 , m ] [1,m] [1,m] 以内的整数解。

    输入格式

    第一行包含 2 2 2 个整数 n 、 m n、m nm,每两个整数之间用一个空格隔开。 接下来的 n + 1 n+1 n+1 行每行包含一个整数,依次为 a 0 , a 1 , a 2 , . . . , a n a0,a1,a2,...,an a0,a1,a2,...,an

    输出格式

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

    输入

    2 10 2 -3 1

    输出

    2 1 2

    说明/提示

    【数据范围】

    对于 100 % 100\% 100%的数据, 0 < n ≤ 100 , ∣ a i ∣ ≤ 1 0 10000 , a n ≠ 0 , m ≤ 1000000 0<n≤100,|ai|≤10^{10000},an≠0,m≤1000000 0<n100ai1010000an=0m1000000


    题目分析

    这道题显然不能打暴力, 但可以用秦九韶算法将 a 0 + a 1 ∗ x + a 2 ∗ x 2 + . . . + a n ∗ x n = 0 a0+a1*x+a2*x^2+...+an*x^n=0 a0+a1x+a2x2+...+anxn=0 转化为 ( … ( ( a n x + a n − 1 ) x + a n − 2 ) x + . . . + a 1 ) x + a 0 = 0 (…((a_nx+a_{n-1})x+a_{n-2})x+...+a_1)x+a_0=0 (((anx+an1)x+an2)x+...+a1)x+a0=0 我们只需要枚举 1 1 1 m m m 中的每一个答案,然后代入方程式判断即可。 (注:别忘了开 l o n g long long l o n g long long

    code

    #include<cstdio> #include<iostream> #include<algorithm> #define MOD 998244353 using namespace std; bool flag; long long n,m,t; long long a[101],ans[1000039]; template<typename T>void read(T &a){ T x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();} while(isdigit(ch)){x=((x<<1)%MOD+(x<<3)%MOD+ch-'0')%MOD;ch=getchar();} a=f?x:-x; } inline bool js(long long x){ long long sum=0,i; for(i=n;i;i--) sum=((a[i]+sum)*x)%MOD; sum=(sum+a[0])%MOD; return !sum; } int main(){ read(n);read(m); long long i; for(i=0;i<=n;i++) read(a[i]); for(i=1;i<=m;i++) if(js(i)) ans[++t]=i; printf("%lld\n",t); for(i=1;i<=t;i++) printf("%lld\n",ans[i]); return 0; }
    Processed: 0.010, SQL: 8