POJ1006 - Biorhythms(중국의 잉여 정리)

2985 단어 poj

제목의 대의.


생략중국어가 있어요.

문제풀이


여방정식 그룹을 푸는 거예요.
x≡(p-d)(mod 23)
x≡(e-d)(mod 28)
x≡(i-d)(mod 33)
가장 간단한 중국 잉여정리 응용...

코드:

#include<iostream>

#include<cstdio>

using namespace std;

void gcd(int a,int b,int &d,int &x,int &y)

{

    if(!b)

    {

        d=a,x=1,y=0;

    }

    else

    {

        gcd(b,a%b,d,y,x),y-=x*(a/b);

    }

}

int main()

{

    int p,e,d,i,a1,a2,a3,M1,M2,M3,t=0;

    while(cin>>p>>e>>i>>d&&p+e+i+d>=0)

    {

        int x=0,y,q;

        a1=p-d,a2=e-d,a3=i-d;

        M1=924,M2=759,M3=644;

        gcd(23,M1,q,q,y),x=(x+y*M1*a1)%21252;

        gcd(28,M2,q,q,y),x=(x+y*M2*a2)%21252;

        gcd(33,M3,q,q,y),x=(x+y*M3*a3)%21252;

        x=(x%21252+21252)%21252,x=x?x:21252;

        printf("Case %d: the next triple peak occurs in %d days.
",++t,x); } return 0; }

좋은 웹페이지 즐겨찾기