自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:12:16，当前版本为作者最后更新于2019-10-13 16:48:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

放一篇不太一样的题解（大雾

首先考虑将题目转化成图论模型，让 $i$ 向 $i^k$ 连一条边，然后可以发现这样会连出来很多张独立的图，容易发现每张图的贡献独立，所以加起来即可

然后会发现这些图都长一个样

不妨设当前被考虑到的点为 $x$，那么此时图中应该有$x^2,x^3,x^4,...x^k$

然后会发现这些图对于答案的贡献之和此图的大小有关，而图的大小又是$\log$级的

于是问题转化为给定一个大小为$x(x\le 30)$的图，每次可以随机删掉一个数和其倍数，求删完的期望次数。

就会想到写个状压去算某一张图的贡献...

当然状压的确是可以将答案算出来的，但是复杂度是$O(2^{30})$而且空间开销相同所以本机是完全跑不出来的...(至少我这里是

于是就会想到真的需要的$dp$值只有$dp[1_2],dp[11_2],dp[111_2]...dp[111111...111_2]$

然而这些状态实际上依赖的状态存在大量相同而且真正有效的$dp$不多所以可以用一个$\rm map$将有效的$dp$存下来

但是这样还是很慢

所以就会想到要打表

提前用$dp$将图的大小为$x$的时候的期望算出来，然后枚举一个数$x$计算出图的大小并将被用到的点标记，单次复杂度$O(n)$

但是实际上对于某一个$x$如果$x>\sqrt n$且不存在一个$i$满足$i^k=x$那么显然 $x$ 对于答案的贡献为$1$

于是真正要计算的点就只有$1-\sqrt n$的这些数

复杂度大约是$O(T\sqrt n)$

然后要特判$1$

$Code:$

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register 
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 35000 ; 
const int M = 35 ;
double Ans[M] = { 0, 1.0, 1.5, 2.0, 2.33333333333333, 2.83333333333333, 3.08333333333333,
3.5833333333333, 3.8333333333333, 4.16666666666667, 4.4166666666667, 4.91666666666667, 5.08333333333333, 5.58333333333333,
5.8333333333333, 6.0833333333333, 6.28333333333333, 6.7833333333333, 6.95, 7.45, 7.61666666667, 
7.8666666666667, 8.11666666666667, 8.6166666666667, 8.741666666667, 9.075, 9.325, 9.575, 9.741666666667,
10.2416666666667, 10.3666666666667 };
int n, vis[N], rU ;  
signed main()
{
	int T = gi() ;
	while( T-- ) {
		n = gi() ; int cnt = sqrt(n), k = 0, j ;
		if( cnt * cnt <= n ) ++ cnt ; 
		double ans = 1 ; rU = n - cnt ;
		memset( vis, 0, sizeof(vis) ) ;
		rep( i, 2, cnt ) {
			if( vis[i] ) continue ; 
			for( j = i, k = 0; j <= n; j *= i, ++ k ) {
				if( j > cnt ) -- rU ; 
				else vis[j] = 1 ; 
			} ans += Ans[k] ; 
		} 
		if( cnt <= n ) printf("%.8lf\n", ans + rU ) ;
		else printf("%.8lf\n", ans ) ;
	} 
	return 0 ;
}

打表程序：

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int M = 35 ; 
double Ans[M] ; 
int m ; 
int get( int x ) {
	int ans = 0 ; 
	while( x ) ans += ( x & 1 ), x >>= 1 ;
	return ans ; 
}
map<int, double> dp ;
double Dp( int i ) {
	if( dp[i] || i == 0 ) return dp[i] ; 
	int len = get(i) ;
	for( re int j = 1; j <= m; ++ j ) {
		if( ( 1 << ( j - 1 ) ) & i ) {
			int rk = 0 ;
			for( re int k = j; k <= m; k += j ) {
				if( ( 1 << ( k - 1 ) ) & i ) rk |= ( 1 << ( k - 1 ) ) ;
			}
			dp[i] = ( dp[i] + ( 1.0 / len ) * ( 1.0 + Dp(i ^ rk) ) ) ;
		}
	}
}
signed main()
{
	
	m = 30 ; int maxn = ( 1 << m ) - 1, rnt = 1 ; 
	printf("%d\n", m ) ;
	for( re int rnt = 1; rnt <= m; ++ rnt ) {
		printf("%d %.8lf\n", rnt, Dp( ( 1 << rnt ) - 1 ) ) ; 
	}
	return 0 ;
}