[noip] 방정식 을 푸 는 진 구 소 알고리즘

방정식 을 풀다
묘사 하 다.
이미 알 고 있 는 다항식 방정식: a0 + a1x1 + a2x 2.
입력 형식
총 n + 2 줄 을 입력 하 십시오.첫 번 째 줄 은 두 개의 정수 n, m 를 포함 하고 두 개의 정수 사 이 를 하나의 빈 칸 으로 구분한다.다음 n + 1 줄 은 줄 마다 하나의 정 수 를 포함 하고 a0, a1, a2,..., an 순 으로 나 뉜 다.
출력 형식
첫 번 째 줄 의 출력 방정식 은 [1, m] 내의 정수 해 의 개수 이다.그 다음 에 각 줄 의 정 수 는 작은 것 에서 큰 것 까지 순서대로 방정식 을 출력 하고 [1, m] 안의 정수 해 를 출력 한다.
샘플 입력 1
2 10 1 -2 1
샘플 출력 1
1 1
샘플 입력 2
2 10 2 -3 1
샘플 출력 2
2 1 2
샘플 입력 3
2 10 1 3 2
출력
0
제한 하 다.
30% 의 데이터 에 대해 0 < n ≤ 2, | ai | ≤ 100, anan ≠ 0, m ≤ 100;50% 의 데이터 에 대해 0 < n ≤ 100, | ai | ≤ 10100, an ≠ 0, m ≤ 100;70% 의 데이터 에 대해 0 < n ≤ 100, | ai | ≤ 1010000, an ≠ 0, m ≤ 10000;100% 의 데이터 에 대해 0 < n ≤ 100, | ai | ≤ 1010000, an ≠ 0, m ≤ 1000000.
근원
NOIP 2014 승급 팀 Day 2
이 문 제 를 보 니 무섭다. 1010000?!얼마나 큰 숫자 입 니까? 높 은 정밀도 입 니까?시간 초과 할 거 야. 어떻게 해?먼저 반드시 진 구 소 산법 을 써 야 한다. 그렇지 않 으 면 쓰기 가 느 릴 뿐만 아니 라 매우 힘들다.
진 구 소 알고리즘:
f (x) = a0 + a1x1 + a2x 2.방정식 을 검증 하고 쓰기 도 쉽 지만 숫자 가 매우 크다. 높 은 정밀도 로 set 를 쓸 수 없 는 나 는 매일 하 쉬 를 폭력 한다. 이것 은 나 로 하여 금 모두 같은 방정식 을 쓸 수 있다 는 것 을 직접적 으로 생각 하 게 한다. 양쪽 에 각각 하나의 질 수 를 가지 게 한다. 만약 에 원 방정식 의 계산 결과 가 0 이 라면 모델 은 앞으로 도 0 이 고 그 다음 에 몇 개의 질 수 를 더 취하 면 충돌 을 피 할 수 있다. 70% 가 넘 으 면 T 는 30% 를 최적화 해 야 한 다 는 것 이다.동 여 방정식 이 떠 오 르 면 자 연 스 럽 게 뒤에 있 는 것 이 생각 납 니 다. f (x) 1. 1. 1. f (x + p) (modp). 그러면 우 리 는 1 ~ m 가 아 닌 1 ~ p 로 계산 합 니 다. p 는 3 ~ 5 개의 2 만 원 정도 의 질 수 를 취하 면 충돌 을 피 할 수 있 습 니 다. 코드 를 보면 간단 합 니 다. 주석 을 쓰 지 않 았 습 니 다.

#include
#include
#include
#define ll long long

using namespace std;
ll a[4][105],x,m,n,k,b[4][1000005],p[4]={0,10007,23333,11261};
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        string s;
        cin>>s;
        int len=s.size(),flag=0;
        if(s[0]=='-')flag=1;
        for(int j=flag;j1][i]=(a[1][i]*10+s[j]-'0')%p[1];
            a[2][i]=(a[2][i]*10+s[j]-'0')%p[2];
            a[3][i]=(a[3][i]*10+s[j]-'0')%p[3]; 
        }
        if(flag)
        {
            a[1][i]=-a[1][i];
            a[2][i]=-a[2][i];
            a[3][i]=-a[3][i];
        }
    }
    for(int k=1;k<=3;k++)
    {
        for(int i=1;i
int t=a[k][n];
            for(int j=n-1;j>=0;j--)
                t=(t*i+a[k][j])%p[k];
            if(t==0)b[k][i]=1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        b[0][i]=1;
        for(int j=1;j<=3;j++)
        if(!b[j][i%p[j]])b[0][i]=0;
    }
    int num=0;
    for(int i=1;i<=m;i++)
        if(b[0][i])num++;
    cout<'
';
    for(int i=1;i<=m;i++)
        if(b[0][i])printf("%d
",i);
    return 0;
}

대충 이 모양 입 니 다. 질문 이나 오류 가 있 으 면 댓 글 에 '감사합니다.'