题解：P5134 好编号

· · 题解

题目传送门。

思路

首先题目要求 \frac{A}{K^i} -\lfloor\frac{A}{K^i}\rfloor>\frac{A}{K^N}，经过一定转换后可得到 A\bmod K^i >\frac{A}{K^{N-i}}，这种形式的式子让我们不难想到将 A 看成一个长度为 N 的 K 进制数，也就是对于每个 i，均满足该 K 进制数的后 i 位大于它的前 i 位。

问题相当于求有多少个长度为 N，字符集为 K，其后缀数组满足 rank_1=1 的方案数，容易发现：

于是计数，令 f_i 表示长度为 i 串中有多少合法的串，有转移：

f_i=k^i-\sum_{j\mid i,j\not=i} f_j

最后得到的 f_n 每个合法串会重复计算 n 遍，所以最后除个 n 即可，直接做是 \mathcal O(\tau(n^2))，可以优化到 \mathcal O(\tau(n)\omega(n))。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Mod=1e9+7;
int n,k;
vector<int>divs;
map<int,int>f;

inline ll ksm(ll a,int b,int mod){
    ll z=1;
    while(b){
        if(b&1) z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i*i<=n;i++){
        if(!(n%i)){
            divs.emplace_back(i);
            if(i*i!=n) divs.emplace_back(n/i);
        }
    } 
    sort(divs.begin(),divs.end());
    for(auto i:divs){
        f[i]=ksm(k,i,Mod);
        for(auto j:divs)
            if(!(i%j) and i!=j)
                f[i]=(f[i]-f[j]+Mod)%Mod;
    }
    printf("%lld",f[n]*ksm(n,Mod-2,Mod)%Mod);

    system("pause");
    return 0;
}