题解：CF2215B RReeppeettiittiioonn

· · 题解

跑得飞快的题解，记录。

根据题意，如果在 b 进制下，n 由若干个长度为 p 且数字全相同的块组成（且 p > 1），则 n 一定满足特定形式。

设每块的数字为 D_i（显然 0 \le D_i < b 且最高位不为 0），则一个块的值为：D_i \cdot b^{p-1} + D_i \cdot b^{p-2} + \dots + D_i = D_i \frac{b^p - 1}{b - 1}。

因此，n 可以提取出公因子 \frac{b^p - 1}{b - 1}：

n = \frac{b^p - 1}{b - 1} \sum_{i=0}^{m-1} D_i (b^p)^i

令 f(b, p) = \frac{b^p - 1}{b - 1}，且设 B = b^p。可以看出，n 必须是 f(b, p) 的倍数。令 Y = \frac{n}{f(b, p)}，那么 Y 实际上就是由 D_i 组成的在 B 进制下的数值：Y = \sum D_i B^i。

满足题意的充要条件是：f(b, p) 是 n 的约数，并且商 Y 在 B 进制下的所有位均严格小于 b。

我们可以找出 n 的所有约数 d，并针对约数逆推 (b, p)：

  1. 当 p = 2 时：d = f(b, 2) = b + 1 \implies b = d - 1。要求 b \ge 2，即 d \ge 3。此时 B = b^2。我们可以特判优化：如果 d > \sqrt{n}，则商 Y < d，此时 Y 在 B 进制下只有 1 位，只要满足 Y < b 即合法，免去了除法循环。

  2. 当 p = 3 时：d = f(b, 3) = b^2 + b + 1 \implies b^2 + b = d - 1。我们可以 O(1) 判定是否存在正整数 b 满足 b(b+1) == d - 1。如果存在，再判定 Y 在 B = b^3 进制下是否合法。

  3. 当 p \ge 4 时：因为 n \le 10^{12}，所以 b \le 10000（因为 10000^4 > 10^{12}）。满足条件的 f(b, p) \le 10^{12} 的 (b, p) 对数量极少（大约一万多个）。我们可以预处理这些值并存入 map，对约数 d 直接 O(1) 查表。

我们使用预处理质数筛，然后利用 DFS 快速生成 n 的所有约数。

:::info[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
bool f[N];
vector<int> g;
// 预处理 p >= 4 的 f(b, p)
map<int,vector<pair<int,int> > > pre;
vector<int> v;
vector<pair<int,int> > a;
void dfs(int u,int w){
    if(u==a.size()){
        v.push_back(w);
        return;
    }
    int p=a[u].first;
    int cnt=a[u].second;
    int mul=1;
    for(int i=0;i<=cnt;i++){
        dfs(u+1,w*mul);
        if(i<cnt)
            mul*=p;
    }
    return;
}
void solve(){
    int n;
    cin>>n;
    if(n<=2){
        cout<<0<<'\n';
        return;
    }
    int t=n;
    // 快速分解质因数
    a.clear();
    for(int p:g){
        if(p*p>t)   break;
        if(t%p) continue;
        int cnt=0;
        while(t%p==0){
            cnt++;
            t/=p;
        }
        a.push_back(make_pair(p,cnt));
    }
    // DFS 生成所有约数
    if(t>1) a.push_back(make_pair(t,1));
    v.clear();
    dfs(0,1);
    int ans=0;
    // 对每个约数反推判定
    for(int d:v){
        // 情况 1：p = 2
        if(d>=3){
            int b=d-1;
            int Y=n/d;
            if(d*d<=n){
                int b2=b*b;
                int x=Y;
                bool F=1;
                while(x){
                    if(x%b2>=b){
                        F=0;
                        break;
                    }
                    x/=b2;
                }
                ans+=F;
            } else{
                // 此时 Y < d 必定成立，由于 Y = d - 1 等价于最高位不合法，所以判断严格小于
                if(Y<b)
                    ans++;
            }
        }
        // 情况 2：p = 3
        int f3=d-1;
        if(f3>=6){
            int b=sqrt(f3);
            while((b+1)*(b+2)<=f3)  b++;
            while(b*(b+1)>f3)   b--;
            if(b>=2&&b*(b+1)==f3){
                int Y=n/d;
                int B=b*b*b;
                int x=Y;
                bool F=1;
                while(x){
                    if(x%B>=b){
                        F=0;
                        break;
                    }
                    x/=B;
                }
                ans+=F;
            }
        }
        // 情况 3：p >= 4
        if(pre.count(d)){
            for(auto& pair:pre[d]){
                int b=pair.first;
                int p=pair.second;
                int Y=n/d;
                int B=1;
                for(int i=0;i<p;i++)
                    B*=b;
                int x=Y;
                bool F=1;
                while(x){
                    if(x%B>=b){
                        F=0;
                        break;
                    }
                    x/=B;
                }
                ans+=F;
            }
        }
    }
    cout<<ans<<'\n';
    return;
}
signed main(){
    // 预处理所有 b>=2, p>=4 且 f(b, p) <= 10^12 的可能取值
    memset(f,1,sizeof(f));
    f[0]=f[1]=0;
    for(int i=2;i<N;i++){
        if(!f[i])   continue;
        g.push_back(i);
        for(int j=i+i;j<N;j+=i)
            f[j]=0;
    }
    for(int i=2;i<=10000;i++){
        int res=1+i+i*i;
        int sum=i*i;
        for(int p=4;;p++){
            sum*=i;
            res+=sum;
            if(res>1000000000000LL) break;
            pre[res].push_back(make_pair(i,p));
        }
    }
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

:::

复杂度分析

因此，单用例的最坏运算次数 \approx 10^4，总计 1000 个测试用例，总操作级别在 10^7 左右。

PS：使用我的解法数据可以加强到 \sum n \le 10^{18}。