[翻譯]2014 1C A.Part Elf

Sylveon

https://code.google.com/codejam/contest/3004486/dashboard#s=p0

突然看到GCJ開始，沒報名，就幫翻譯吧！

大意：我們稱每個人都有可能是隻小精靈後代，我們可以用分數 P/Q 來表示有多少比例的小精靈血緣。如果有兩個人結婚，後代的小精靈血緣為親代的算術平均數(A+B)/2。我們訂純種的小精靈血緣比例是1/1，所有最初的親代要嘛是 1/1 要嘛是 0/1 ，今天有一個人知道自己的小精靈血緣比例，他想知道跟他最親的純種小精靈祖先相差幾代，如果超過40代都不存在的話就當作不存在。

輸入說明：
第一行有一個數字T，表示接下來有幾筆測資。每筆測資以P/Q的方式輸入，代表詢問的比例。

Small  [tex]1%5Cleq%20P%2CQ%20%5Cleq100[/tex],[tex]GCD(P,Q)=1[/tex]
Large [tex]1%5Cleq%20P%2CQ%20%5Cleq10%5E%7B12%7D[/tex],[tex]GCD%28P%2CQ%29%5Cneq%201[/tex]

範例輸入：
5
1/2
3/4
1/4
2/23
123/31488範例輸出：
Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8題解：
1.顯然的應該要先約分。
2.Q約分後要是2的冪次才有解
3.猜想：找最小的K滿足 [tex]%5Cfrac%7BP%7D%7BQ%7D%5Cgeq%202%5E%7B-k%7D[/tex]，先說這是我亂猜的(事實上好像就是這樣)。

測資說明


如測資一：1/2
可以化為[tex](0/1+1/1)/2[/tex]，故解為1

如測資二：3/4
可以化為[tex](1/1+1/4)/2[/tex]，1/4又可以化為[tex](1/2+1/2)/2[/tex]，但注意我們要「最接近」的1/1，雖總深度為三，但答案是1。

如測資五：123/31488
約分後為1/256，深度為8

domen111

既然你都寫的那麼完整了，看來我可以省發這題的解題文了
附上我的AC Code

#include<bits/stdc++.h>

using namespace std;

long long p,q;

void input()

{

        scanf("%lld/%lld",&p,&q);

        long long gcd=__gcd(p,q);

        p/=gcd;

        q/=gcd;

}

bool checkQ(long long n)

{

        while(n!=0)

        {

                if(n!=1 && n&1!=0)

                        return false;

                n>>=1;

        }

        return true;

}

int main()

{

        int T;

        cin>>T;

        for(int no=1;no<=T;no++)

        {

                input();

                if(!checkQ(q))

                {

                        printf("Case #%d: impossible\n",no);

                        continue;

                }

                int ans=1;

                while(q/2>p)

                {

                        q/=2;

                        ans++;

                }

                printf("Case #%d: %d\n",no,ans);

        }

}