CF1036F Relatively Prime Powers 题解

标签：CF1036F prime ge1 int 题解 LL Prime mu pow

题目分析

对于一个不合法的数 \(x(x\ge 2)\)，设 \(x=\prod p_i^{r_i}\)，令 \(g=\gcd(r_1,r_2,\ldots,r_k)\)，则 \(x=\left(\prod p_i^{r_i/g}\right)^g\)，所以 \(x\) 是一个正整数的 \(g\) 次方。

所以可以枚举上文的 \(g\)，把每一类不合法方案排除掉，就是答案。

设 \(f(i)\) 表示 \(2\) 到 \(n\) 中 \(i\) 次方数的个数，根据容斥原理，最终答案为：

\[f(1)-\sum_{i\ge1,i\in\text{prime}}f(i)+\sum_{i\ge1,j\ge1,i\ne j,i\in\text{prime},j\in\text{prime}}f(i \cdot j) \cdots \]

即总数减奇数个质数相乘的 \(f\) 值，加偶数个质数相乘的 \(f\) 值。

用莫比乌斯函数 \(\mu\) 可以更简单地表示这个式子：

\[\quad\sum_{i\ge1}\mu(i) \cdot f(i) \]

\(f(i)\) 的计算也很简单：

\[f(i)= \sqrt[i]n - 1 \]

但是这里有个细节问题：如果直接用 c++ 的 pow 函数开方，会出现精度问题，影响答案，这是这道题一个很恶心的地方。具体解决方案如下：

1. 对于求 \(\sqrt[k]n\)，初始用 pow 函数计算出比 \(\sqrt[k]n\) 大的值，具体地，将用 pow 算出的值加 2。

2. 设刚才算出的值为 \(t\)，\(t^k>n\) 则将 \(t\) 减 1。

3. 求 \(t^k\) 用快速幂，中间过程的变量用 long double 存。

示例代码

#include <bits/stdc++.h>

using namespace std;

typedef long double LD;
typedef long long LL;

const int N = 70;

int prime[N], cnt;
int mu[N];
bool st[N];

void init()
{
	mu[1] = 1;
	for(int i = 2; i < N; i ++ )
	{
		if(!st[i])
		{
			prime[ ++ cnt] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= cnt && i * prime[j] < N; j ++ )
		{
			int x = i * prime[j];
			st[x] = true;
			if(i % prime[j] == 0)
			{
				mu[x] = 0;
				break;
			}
			mu[x] = -mu[i];
		}
	}
}

LD ksm(LD a, int n)
{
	LD res = 1.0;
	while(n)
	{
		if(n & 1) res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}

LL solve(int k, LL n)
{
	if(k == 1) return n - 1;
	LL q = (LL)pow(n, 1.0L / k) + 2;
	while(ksm(q, k) > n) q -- ;
	return q - 1;
}

int main()
{
	init();
	int T;
	scanf("%d", &T);
	while(T -- )
	{
		LL n, res = 0;
		scanf("%lld", &n);
		
		for(int i = 1; i <= 60; i ++ )
			if(mu[i])
				res += mu[i] * solve(i, n);
		printf("%lld\n", res);
	}
	return 0;
}

标签：CF1036F,prime,ge1,int,题解,LL,Prime,mu,pow
From： https://www.cnblogs.com/recollect-the-past/p/17981256