noip2014 解方程

- 206通过
- 1.7K提交
题目提供者该用户不存在
标签数论(数学相关)高精2014NOIp提高组
难度提高+/省选-

提交该题讨论题解记录

题目描述

已知多项式方程：

a0+a1x+a2x^2+..+anx^n=0

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

输入输出格式

输入格式：

输入文件名为equation .in。

输入共n + 2 行。

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

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

输出格式：

输出文件名为equation .out 。

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

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

输入输出样例

输入样例#1：

输出样例#1：

1
1

输入样例#2：

输出样例#2：

2
1
2

输入样例#3：

输出样例#3：

说明

30%:0<n<=2,|ai|<=100,an!=0,m<100

50%:0<n<=100,|ai|<=10^100,an!=0,m<100

70%:0<n<=100,|ai|<=10^10000,an!=0,m<10000

100%:0<n<=100,|ai|<=10^10000,an!=0,m<1000000

分析：很容易想到O(n)枚举，只是计算需要高精度，很难打，一个概率性的做法就是mod一个数，如果等于0，那么就有可能是解，mod一个数还不够，需要多mod几个，也不能过多，否则会T,一般是mod两个大小相差比较大的质数.当然，也可以试试自然溢出.

避免高精度可以模一个数，只不过有几率会错.如果只是想输出的话，可以记录一下模数在答案中出现了多少次，合并上答案就行了，例如模数=1e16.答案就是:

Printf(“%lld%016lld”,cnt,ans);

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

char s[10010];
int p[3], n, m;
long long a[3][105];
bool can[1000010];

void quyu(char *s1, int k)
{
    bool fu = false;
    int len = strlen(s1), i;
    for (int j = 1; j <= 2; j++)
    {
        i = 0;
        if (s1[0] == '-')
        {
            fu = true;
            i = 1;
        }
        for (; i < len; i++)
            a[j][k] = (a[j][k] * 10LL % p[j] + s[i] - '0') % p[j];
        if (fu == true)
            a[j][k] = p[j] - a[j][k];
    }
}

int panduan(int x, int k)
{
    long long ans = 0, b = 1;
    for (int i = 0; i <= n; i++)
    {
        ans = (ans + 1LL * a[k][i] * b) % p[k];
        b = 1LL * b * x % p[k];
    }
    return ans % p[k];
}

int main()
{
    p[1] = 67891, p[2] = 1000000207;  //两个质数
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        can[i] = false;
    for (int i = 0; i <= n; i++)
    {
        scanf("%s", s);
        quyu(s, i);           
    }
    for (int i = 1; i <= p[1]; i++)
    {
        if (panduan(i, 1) != 0)
            continue;
        for (int j = i; j <= m; j += p[1])
            if (panduan(j, 2) == 0)
                can[j] = true;
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        if (can[i])
            ans++;
    printf("%d
", ans);
    for (int i = 1; i <= m; i++)
        if (can[i])
            printf("%d
", i);

    return 0;
}