传送门：点击打开链接
很明显会有大量重复的被计算，所以很容易就想到容斥定理。
我们设dp[i]表示能表示成M^i(i>1)且i是这个数字能表示出来的最大的情况时的总类数
比如，27拆成M^K时的K最大能表示成3，所以27这个数字分在dp[3]这一类
1我们暂时不考虑，不把它放在任何一类
因为K>1，所以K至少是2，最大是2^K=N的时候，所以K最大等于log2(N)，所以K非常的小
首先，求出K最大大概的位置
然后开始求dp[i]。求法如下：
首先，1~N中有哪些是能拆分成M^i的，利用pow函数可以算出来，暂时记为dp[i]
按照dp[i]的要求，还必须要排除K目前不是表示最大的情况，相当于容斥了，如下
dp[i]=dp[i]-dp[2*i]-dp[3*i]-dp[4*i]-.......
这样处理完后，dp[i]就是能表示成M^i(i>1)且i是这个数字能表示出来的最大的情况时的总类数了
最后的答案就是dp[2]+dp[3]+....+dp[K的最大值]，再加上我们之前没考虑的1就可以了
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e3 + 5;
const double exps = 1e-8;LL dp[MX];int main() {LL n;//FIN;while(~scanf("%I64d", &n)) {memset(dp, 0, sizeof(dp));int p = ceil(log2(1.0 * n)) + 1;LL ans = 1;for(int i = p; i >= 2; i--) {dp[i] = pow(1.0 * n, 1.0 / i) - 1 + exps;for(int j = 2 * i; j <= p; j += i) {dp[i] -= dp[j];}ans += dp[i];}printf("%I64d\n", ans);}return 0;
}