NOIP 2012 提高組 複賽 day2 mod 同餘方程

 NOIP 2012 提高組 複賽 day2  mod 同餘方程

1.一看題目，還好數論裡瞄過，沒被數學符号給吓到，要不要将數論書再翻一翻，還是将該題AC了再說。

2.數學有儲備，見了該題就不慌了。

3.看了該題，心裡明白，一不小心就容易資料溢出，為了争取盡可能多的分，long long是免不了了。心裡有個小九九，用C來寫，寫好後，正好去linux下用Arbiter進行測試，看看對%lld的支援。

4.簡單做了運算int 最大值2*10^9 long long 最大值4*10^9*10^9，運算過程中随時注意取模，應該不會溢出。

5.編寫代碼，送出50分，剩下5個資料，全報TLE，逾時了。

6.突然間想到一個辦法，思路來自(10*2+1)/3=7，送出60分，剩下4個資料，全報TLE，逾時了。

7.網絡中搜尋了一下，說是擴充歐幾裡德算法，好吧，開始學習。

8.翻書的過程中發現，關于資訊學的書涉及的數學，比純數學的書涉及的數學，講解得更具體，更接近計算機的具體實作。故，翻書的順序，先翻資訊學的書，要擴充，完畢知識時，再翻純數學的書。

9.學習一天未果，好吧，上代碼學習，并進行相應跟蹤。

10.稀裡糊塗的編碼，用的是擴充歐幾裡德算法，測試樣例發現是-3，果斷加上10，簡單修改代碼，送出AC。

11.還是要弄明白原理。再學習學習。

12.關于擴充歐幾裡德算法，這兩篇文章介紹得不錯，建議先閱讀第一篇，之後第二篇。

http://www.cnblogs.com/ka200812/archive/2011/09/02/2164404.html

http://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html

13.2011年時POJ1061青蛙的約會，比較流行，也即擴充歐幾裡德算法，2012年進行改編成為NOIP提高組複賽day2第一題。

附上AC代碼，編譯環境Dev-C++4.9.9.2

//2012 mod3

#include <stdio.h>

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 a,b,d,x,y;

    scanf("%d%d",&a,&b);

    gcd(a,b,d,x,y);

    while(x<0){

        x+=b;

    }

    printf("%d\n",x);

    return 0;

}

附上60分代碼，編譯環境Dev-C++4.9.9.2

//2012 同餘方程 mod2

#include <stdio.h>

int main(){

    long long a,b,i,j;

    scanf("%lld%lld",&a,&b);

    i=1;

    while(1){

        if((b*i+1)%a==0)

            break;

        i++;

    }

    printf("%lld\n",(b*i+1)/a);

    return 0;

}

附上50分代碼，編譯環境Dev-C++4.9.9.2

//2012 同餘方程

#include <stdio.h>

int main(){

    long long a,b,i,t,j;

    scanf("%lld%lld",&a,&b);

    i=1;

    t=a;

    t%=b;

    while(1){

        j=i;

        j%=b;

        if((t*j)%b==1)

            break;

        i++;

    }

    printf("%lld\n",i);

    return 0;

}

附上poj1061青蛙的約會AC代碼，編譯環境Dev-C++4.9.9.2（很多小的細節）

//poj1061 青蛙的約會

#include <stdio.h>

void gcd(long long a,long long b,long long &d,long long &x, long long &y){

    if(!b){

        d=a;

        x=1;

        y=0;

    }else{

        gcd(b,a%b,d,y,x);

        y-=a/b*x;

    }

}

int main(){

    long long a,b,d,x,y,b2;

    long long t1,t2,t3,t4,t5;

    scanf("%lld%lld%lld%lld%lld",&t1,&t2,&t3,&t4,&t5);

    a=t3-t4;

    b=t5*-1;

    gcd(a,b,d,x,y);

    if((t2-t1)%d!=0){

        printf("Impossible\n");

    }else{

        b2=b/d;

        x=((t2-t1)/d*x%b2+b2)%b2;

        printf("%lld\n",x);

    }

    return 0;

}