题意

给定一个整数N,请你求出有多少字符集为1到K之间整数的字符串，使得该字符串可以由一个长度为N的回文串循环移位后得到。所谓循环移位，就是把字符串的某个前缀（可以为空）移到字符串末尾，如"1221"循环移位可以得到"1221"、"2211"、"2112"、"1122"四个字符串。结果对$10^9+7$取模

题解

考试时花了差不多一个小时推了一个$O(n)$的式子，还妄想着能优化到$O(sqrt(n))$......

首先，考虑一个回文串对答案的贡献：

设其最小循环节长度为len。

其贡献就是len。

但是一个回文串的循环节必定也是回文串（想不明白可以看这个：abcabcabc）

所以对于len为偶数的情况，循环节可以从中间拆开，这就导致了互换前后段后相同的循环节，例如2112,1221会扩展出一样的结果，所以要此时贡献要除以2.

但对于长度为奇数的情况，由于有中间的一位，所以互换前后段后扩展出来的仍是不同的结果，所以不用除以2。

因为len相同的回文串对答案的贡献相同，所以对于每一个len,统计代表的回文串个数即可。

又因为len一定是n的因数（不然何来循环），所以直接根号n预处理出n的因数即可。

代码

#include 
#include 
#include 
#include 
using namespace std;
#define int long long
#define mod (int)1000000007
#define N 64000
vector vec;
int tot[N];
int pow(int base,int up)
{
	int ans=1;
	while(up)
	{
		if(up&1) ans*=base,ans%=mod;
		base*=base;
		base%=mod;
		up>>=1;
	}
	return ans;
}
signed main()
{
	int n,k,len;
	cin>>n>>k;
	len=sqrt(n);
	for(int i=1;i<=len;i++) if(n%i==0)//获取所有可能的循环节长度
	{
		vec.push_back(i);
		if(i!=n/i) vec.push_back(n/i);
	}
	sort(vec.begin(), vec.end());
	int ans=0;
	for(int i=0;i