[校内集训]小秋数数

题意

小秋想要知道有多少个数组(a_1,a_2,...,a_k)满足(gcd(a_1,a_2,...,a_k)=d)并且(lcm(a_1,a_2,...a_k)=n)，两个数组视为不同，只要存在一个位置两个数不同

思路

虽然这道题并不是原创题

将(d,n)质因数分解，对于每一个质因子，至少一个数的因子为最小，至少一个数的因子为最大，用容斥即可，即全集-一个不满足+两个不满足

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int k,d,n;

ll quickpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
int main()
{
	cin>>k>>d>>n;
	ll ans=1;
	for(int i=2;i*i<=n;++i)
	{
		if(n%i==0)
		{
			int cnt1=0,cnt2=0;
			while(n%i==0) ++cnt1,n/=i;
			while(d%i==0) ++cnt2,d/=i;
			if(cnt1==cnt2) continue;//注意判相等
			ans = ans * ((quickpow(cnt1-cnt2+1,k) - 2ll * quickpow(cnt1-cnt2,k) + quickpow(cnt1-cnt2-1,k))%mod) %mod;
		}
	}
	if(d==1 && n>1) ans = ans * (quickpow(2,k)-2) %mod;
	cout<<(ans%mod+mod)%mod<<endl;
	return 0;
}