TIOJ 1135 2.止不住的迴圈

poao899    -4K    15MS    G++     0.84K     2009-10-13 00:13:42                                           .

這題目(對我而言)好凶狠= =


在此跟TIOJ說聲抱歉吃了我那麼多爛code

58880	poao899	1135	Accepted	-4K	15MS	G++	0.84K	2009-10-13 00:13:42
58879	__	1135	Accepted	-4K	15MS	G++	1.17K	2009-10-13 00:12:59
58878	__	1135	Runtime Error			G++	1.1K	2009-10-13 00:07:52
58877	__	1135	Runtime Error			G++	1.08K	2009-10-13 00:06:26
58874	__	1135	Runtime Error			G++	1.07K	2009-10-12 23:53:43
58873	__	1135	Runtime Error			G++	1.05K	2009-10-12 23:52:55
58872	__	1135	Runtime Error			G++	1.05K	2009-10-12 23:52:37
58870	__	1135	Output Limit Exceed			G++	1.0K	2009-10-12 23:50:44
58869	__	1135	Output Limit Exceed			G++	1.0K	2009-10-12 23:50:26
58868	__	1135	Output Limit Exceed			G++	1.03K	2009-10-12 23:50:03
58867	__	1135	Runtime Error			G++	1.0K	2009-10-12 23:49:28
58865	__	1135	Runtime Error			G++	1.0K	2009-10-12 23:49:07
58864	__	1135	Runtime Error			G++	0.96K	2009-10-12 23:48:34
58863	__	1135	Runtime Error			G++	0.98K	2009-10-12 23:48:19
58862	__	1135	Runtime Error			G++	1.0K	2009-10-12 23:47:57
58861	poao899	1135	Runtime Error			G++	1.01K	2009-10-12 23:47:32
58860	poao899	1135	Runtime Error			G++	1.01K	2009-10-12 23:46:39
58859	poao899	1135	Runtime Error			G++	1.01K	2009-10-12 23:46:16
58856	poao899	1135	Runtime Error			G++	0.96K	2009-10-12 23:40:05

整數線性組合的題目。

簡單紀錄一下解法好了XD


以下雷很大不喜者勿入


輸入有四個數字 a,b,c,k

依題目意思可以知道是找出

a + nc = m(2^k) + b

其中n為正整數,m為整數

整理一下會發現

nc + m(2^k) = b - a

即是做出c跟2^k的線性組合 湊成b-a

然後幾個要點

0. c有可能是0= =    就是這點讓我RE好幾遍QQ

1. 如果 gcd(c,2^k) 不是(b-a)的因數 直接輸出FOREVER

2.線性組合做出來是

pc + q(2^k) = gcd(c,2^k)

兩邊同乘就可以得到(b-a)的線性組合

不過要注意

I. n<0

II. n並非合理之最小  正  整數



大概就這樣了XD


以下code  一堆冗贅東西很礙眼

//********************************************

#include<stdio.h>
long long p,q,n;
long long gcd(long long a,long long b){
    static int x=0;
    if(a%b==0){
        p=0;q=1;
        return b;
    }
    long long c,g;
    long long tp,tq;
    c=a%b;
    g=gcd(b,c);
    n=a/b;
    tp=p;tq=q;
    p=tq;
    q=tp-n*tq;
    return g;
}

//(pow[k]-1)p+cq=gcd()

int a,b,c,k,t;
long long an,bn;
long long pow[64];
main(){
   
    pow[0]=1;
    for(int i=1;i<60;i++)
        pow[i]=pow[i-1]*2;
    scanf("%d",&t);
   
    while(t--){
        scanf("%d%d%d%d",&a,&b,&c,&k);
        if(c==0){
            a==b?puts("0"):puts("FOREVER");
            continue;
        }
        long long g=gcd(pow[k],c);
       
        if(b==a){
            puts("0");
            continue;
        }
        if((long long)(b-a)%g!=0){
            puts("FOREVER");
            continue;
        }
        an=c/g;
        bn=(pow[k])/g;
        long long rp=p*((b-a)/g),rq=q*((b-a)/g);
        if(rq<0){
            rq+=((-rq)-1+bn)/bn*bn;
        }
        rq-=rq/bn*bn;
        printf("%I64d\n",rq);
    }
}