exgcd

发表于 | 分类于 ，

POJ2142The Balance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int exgcd(int a,int b,int &x,int &y){
    if(b==0) {x=1;y=0;return a;}
    int c=exgcd(b,a%b,x,y);
    int z=x;x=y;y=z-y*(a/b);
    return c;
}
int main(){
    int a,b,c;
    // printf("%d\n",__gcd(700,300));
    while(~scanf("%d%d%d",&a,&b,&c)){
        if(a==b&&b==c&&a==0) break;
        int x,y;
        int gcd=exgcd(a,b,x,y);
        // printf("x=%d y=%d\n",x,y);
        int mod=b/gcd;
        int t=c/gcd;
        int x1=(t*x%mod+mod)%mod;
        int y1=(c-a*x1)/b;
        int ans1=abs(x1)+abs(y1);
        // printf("mod=%d x1=%d y1=%d\n",mod,x1,y1);
        mod=a/gcd;
        int y2=(t*y%mod+mod)%mod;
        int x2=(c-y2*b)/a;
        int ans2=abs(x2)+abs(y2);
        // printf("mod=%d x2=%d y2=%d\n",mod,x2,y2);
        if(ans1>ans2){
            printf("%d %d\n",abs(x2),abs(y2));
        }
        else printf("%d %d\n",abs(x1),abs(y1));
    }
}

POJ2115C Looooops

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0) {x=1,y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-y*(a/b);
    return d;
}
int main(){
    ll a,b,c,k;
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k)){
        if(!a&&!b&&!c&&!k) break;
        ll x,y;
        ll l=1;
        l<<=k;
        ll gcd=exgcd(c,l,x,y);
        // printf("gcd=%lld\n",gcd);
        if((b-a)%gcd==0){
            ll t=(b-a)/gcd;
            l/=gcd;
            printf("%lld\n",(t*x%l+l)%l);
        }
        else printf("FOREVER\n");
    }
    //system("pause");
}