自动搬运

查看原文

来自洛谷，原作者为

	Polarisx 一位努力不落后的 NPC

搬运于2025-08-24 22:07:29，当前版本为作者最后更新于2025-05-26 20:54:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门。

思路

首先题目要求 $\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_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;
}