题解 [ARC141A] Periodic Number

cjh20090318 · 2024-09-01 00:17:55 · 题解

一个不怎么需要动脑筋的做法，看了一圈题解区没有一篇题解提到，虽然效率不高但是还是来记录一下。

题意

给定一个正整数 N \ge 11，求不超过 N 最大拥有循环节的数。

分析

因为答案有单调性，所以这种求不超过最大的问题可以二分答案转化为判定性问题。

外层循环枚举循环次数，内部二分重复的数即可。

单次时间复杂度 O(\log_{10}n\log_2{n})，效率比较低。

代码

//the code is from chenjh
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n;
int w(const LL&x){return int(log10((long double)x))+1;}//求正整数位数。
LL p1[20];
LL f(const int x,int t){
    LL ret=0;
    int q=w(x);
    if(q*t>18) return n+1;//位数太多直接返回 n+1。
    while(t--) ret=ret*p1[q]+x;
    return ret;
}
void solve(){
    scanf("%lld",&n);
    LL ans=0;
    for(int i=2,mi=w(n);i<=mi;i++){
        int l=1,r=p1[mi/i+1];
        for(int mid;l<r;) f(mid=(l+r+1)>>1,i)>n?r=mid-1:l=mid;//二分找到最后一个小于等于 n 的数。
        LL k=f(l,i);
        k<=n&&(ans=max(ans,k));//取最大值。
    }
    printf("%lld\n",ans);
}
int main(){
    p1[0]=1;
    for(int i=1;i<=18;i++) p1[i]=p1[i-1]*10;
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}