CF1036F

标签：CF1036F return int ll ret -- while

题目链接

description

\(10^5\) 次询问

每次给定 \(n\leq 10^{18}\), 求 2 到 \(n\) 内质因子分解结果为 \(p_{a_1}^{b_1}p_{a_2}^{b_2}...\)，且 \(\gcd(b1,b2...)=1\) 的数的个数。

solution

显然答案为 \(\sum\limits_{i=1} \mu(i) \lfloor\sqrt[i]{n}-1\rfloor\)。

直接用 cmath 里的 pow 计算的话精度会炸掉。

手写二分会 TLE。

建议先用 pow 得到 \(n\) 的 \(i\) 次方根的粗略取值，然后微调，用快速幂判断（中间如果发现返回值已经大于 \(n\) 了直接返回）。

具体见代码吧。qwq

hint

计算浮点数下取整一定不能忽略精度问题。

code

#include<bits/stdc++.h>

using namespace std;

typedef __int128 ll;

const int N=100;

ll n,miu[100],pw[N][N];

bool chk(ll a,ll b,ll L){
	ll ret=1;
	while(b){
		if(b&1) ret=ret*a;
		if(ret>L) return false;
		a=a*a;
		b>>=1;
	}
	return true;
}

void solve(){
	long long t1;
	cin>>t1;
	n=t1;
	ll v=0,ans=0;
	for(int i=1; ; i++){
		ll v=pow(n,1.0/i);
		while(chk(v,i,n)) v++;
		while(!chk(v,i,n)) v--;
		v--;
		if(v==0) break;
		ans=ans+miu[i]*v;
	}
	cout<<(long long)ans<<endl;
}
/// 100000000000000000
vector<ll> primes;
int st[111];

int main(){

	// . .. . 省略了预处理mobius函数 .. . //
	
	int T;
	cin>>T;
	while(T--) solve();
	
	return 0;
}

标签：CF1036F,return,int,ll,ret,--,while
From： https://www.cnblogs.com/FreshOrange/p/17683348.html