BestCoder Round #75 King’s Cake 模拟&&优化 || gcd

source

The question is from BC and hduoj 5640.

My Solution

//A really easy problem, I get a Runtime Error(STACK_OVERFLOW) first, then Time Limit Exceeded
//next Runtime Error (INTEGER_DIVIDE_BY_ZERO)， and a WA   , Accepted......
//I am really sorry for that.

1、用循环模拟

#include 
#include 
#include 
using namespace std;
int tot;

int main()
{
    int T, l, s, t;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &l, &s);
        if(l < s) swap(l, s);
        tot = 0;
        while(true){
            if(s == 1) {tot += l; break;}
            if( s == 0) break;               //!
            t = l/s;
            l -= t*s;
            if(l < s) swap(l, s);
            tot += t;
        }

        printf("%dn", tot);
    }
    return 0;
}

2、像是求最大公约数，所以每次 $\gcd$ 的时候累加答案即可，复杂度$O(\log \max (n,m)T)$。

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx