BOJ-10253ヘンリー

4948 ワード
boj algorithm テキストリンク

に近づく


  • これは方程式と時間の複雑さを考慮する必要がある問題である.

  • まず,ヘンリー式表現の最初の数を求める方法は以下の通りである.

  • 1 x 1≦abfrac{1}{x^{1}leqfrac{a}{b}x 11≦baを満たす最大x 1 x^1 x 1はbとaの値を知っているので、xx^1 x 1に2を代入してからずっと上昇し、正解を見つけることができます.しかし、これはタイムアウトを招きます.

  • したがって,代入値の部分をO(n)O(n)O(n))からO(1)O(1)O(1)O(1)O(1)に2から減らす必要がある.

  • 整理式でb/a≦x 1 b/aleq x^1 b/a≦x 1を表す場合、O(1)O(1)O(1)だけでx 1 x^1 x 1が分かるので、aがbの倍数ではないことを考慮すると、値に+1を加えるべきです.

  • xx^1 x 1を求めた後、a、bをそれぞれ更新し、aが1になるまで行う.

  • 57=12+??\frac{5}{7} =\frac{1}{2} +\frac{?}{?}75​=21​+??和通分を求めると、ax 1+bfrac{acdotx^1+bcotx^1}bx 1}b\x 1+bの式が得られ、a=a\x 1+ba=a\cdotx^1+a\1+a\x 1+b、b=b\x 1 bx 1 b

  • このとき、aおよびbは、gcd(a,b)をそれぞれのaおよびbに分割することによって、非既約スコアの結果を生じることがある.

    • コード(C+)

    #include <iostream>
#define FIO  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
typedef long long ll;
ll t,a,b;
ll gcd(ll a,ll b){ return b ? gcd(b,a%b):a;}

int main(){
    FIO;
    cin>>t;
    while(t--){
        cin>>a>>b;
        while(a!=1){
            ll tmp = (b%a!=0) ? b/a+1:b/a;
            a = a*tmp-b; b *= tmp;
            ll res = gcd(a,b); a/=res; b/=res;
        }
        cout<<b<<"\n";
    }
    return 0;
}

    結果


    [React] Hook, Props, State
    ES 6学習ノート-Moduleの文法