牛客小白月赛31 G题

牛客小白月赛31 G题

题目链接
首先考虑x=0、x=1、x>y特殊情况
然后考虑x<=y的情况
正常考虑x^k <= y
我的思路是k从1开始遍历，最大不会超过64,但是没有AC。应该是中间过程值会超过long long范围。
看到有人用__int128 过了，试了一下，使用__int128 时k从1开始遍历也能AC。没有用过__int128...
看了别人代码，发现是从y开始往下除以x开始。避免了遍历k超long long的问题，真厉害。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define ll long long
int main() {
    int t; scanf("%d",&t);
    for(int i=1;i<=t;i++) {
        ll x,y;
        cin>>x>>y;
        if(x>y) {
            if(y==0) cout<<"-1\n";
            else printf("0\n");
        }
        else if(x==0 || x==1) {
            printf("-1\n");
        }else {
            ll ans = 0;
            while(y>=x) {
                y/=x;
                ans++;
            }
            cout<<ans<<endl;

//            __int128 ans = 1;
//            for(int i=1; ;i++) {
//                ans *= x;
//                if(ans>y) {
//                    cout<<(i-1)<<endl;
//                    break;
//                }
//            }
        }
    }
    return 0;
}