【洛谷P2231】跳蚤

题目

题目链接：https://www.luogu.com.cn/problem/P2231
题面没有 LaTeX 太丑了，所以直接上题意简述吧。
给出 (n,m)，求有多少个长度为 (n) 的序列，满足序列中所有数均为 ([1,m]) 的整数且数列的 (gcd) 与 (m) 互质。

思路

将 (m) 视作数列第 (n+1) 项，问题转化为有多少个长度为 (n+1) 且最后一项为 (m) 的数列的 (gcd) 是 (1)。
设 (f[i]) 表示整个数列的 (gcd=i) 的方案数。因为整个数列与 (m) 的 (gcd) 一定是 (m) 的因子，所以 (f[i]) 最多只有 (2sqrt{m}) 个位置有元素，所以直接拿一个 unorder_map 存即可。
可以发现 (f[i]=gcd) 为 (i) 的倍数的方案数 (-sum_{i|j,jleq m} f[j])。而前面的那一部分显然等于 (lfloor frac{m}{i} floor^n)，所以我们可以从大到小枚举 (m) 的因子，计算出前面部分，然后用这个因子去贡献它的因子。最终答案即为 (f[1])。
时间复杂度 (O(m))。

代码

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

int n,m;
unordered_map<int,ll> f;

ll fpow(ll x,ll k)
{
	ll ans=1;
	for (;k;k>>=1,x=x*x)
		if (k&1) ans=ans*x;
	return ans;
}

void calc(int x)
{
	f[x]+=fpow(m/x,n);
	for (int i=1;i*i<=x;i++)
		if (x%i==0)
		{
			if (i!=x) f[i]-=f[x];
			if (i*i!=x && i!=1) f[x/i]-=f[x];
		}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i*i<=m;i++)
		if (m%i==0) calc(m/i);
	for (int i=sqrt(m-1);i>=1;i--)
		if (m%i==0) calc(i);
	printf("%lld",f[1]);
	return 0;
}