結果

問題 No.1862 Copy and Paste
ユーザー lmxyue
提出日時 2025-09-03 14:17:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,637 bytes
コンパイル時間 2,254 ms
コンパイル使用メモリ 196,660 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-03 14:17:12
合計ジャッジ時間 3,596 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
#define int __int128 
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using namespace std;
typedef pair<int,int> PII; 
namespace read_and_write{
        int read(){ int x=0; bool flag=1; char ch=getchar();
                while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
                while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
        template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
                while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
                while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
        template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
        template<typename T> void write(T x,bool c=0){ if(x<0){x=-x,putchar('-');}
                static short s[35],top=-1; do{s[++top]=x%10,x/=10;}while(x);
                while(~top) putchar(s[top--]+48); putchar(c? ' ':'\n');}
        template<typename T,typename ...Args> void write(T &Pr,Args &...Prs){write(Pr,1),write(Prs...);}
} using namespace read_and_write;
int ksm(int a,int b)
{
        int ans=1;
        while(b)
        {
                if(b&1)
                ans=ans*a;
                a=a*a;
                b>>=1;
        }
        return ans;
}
bool check1(int a,int b,int K)//<=
{
        int ans=1;
        while(b)
        {
                if(ans>K || a>K)
                return false;
                if(b&1)
                ans=ans*a;
                a=a*a;
                b>>=1;
//                write(ans,a);
        }
        return ans<=K;
}
bool check2(int a,int b,int K)//>=
{
        int ans=1;
        while(b)
        {
                if(ans>=K || a>=K)
                return true;
                if(b&1)
                ans=ans*a;
                a=a*a;
                b>>=1;
        }
        return ans>=K;
}
const int maxn=1e18+5;
const int max_xy=1e9+5;
const int INF=1e36;
int n,T[2];
namespace SubTask2
{
        int LOG_2(int n)
        {
                int left=1,right=n;
                while(left<right)
                {
                        int mid=(left+right+1)>>1;
                        if(check1(2,mid,n))
                        left=mid;
                        else
                        right=mid-1;
                }
                return left;
        }
        int doit(int k)
        {
                int left=1,right=n;
                while(left<right)
                {
                        int mid=(left+right)>>1;
                        if(check2(mid,k,n))
                        right=mid;
                        else
                        left=mid+1;
                }
                int i,now=left*k;
                for(i=1;i<=k;i++)
                {
                        if(check2(left,k-i,n) || check2(left-1,i,n) || ksm(left,k-i)*ksm(left-1,i)>=n)
                        now--;
                        else
                        break;
                }
                return now-k;
        }
        int solve()
        {
                int i,k=LOG_2(n),ans=INF;
//                write(k,1);
                for(i=1;i<=k+1;i++)
                ans=min(ans,i*T[0]+doit(i)*T[1]);
                return ans;
        }
}
signed main()
{
//        freopen("dice.in","r",stdin);
//        freopen("dice.out","w",stdout);
read(T[0],T[1],n);
        //read(n,T[0],T[1]);
//        write(check1(2,1000000000,2134)? 1:0);
        write(SubTask2::solve());
        return 0;
}
/*

???????????x 
          ????y

x+y       2*y
T[0]      T[1]+T[0]




*/
0