题目链接：传送门
求小于等于 n ( n < = 1 0 18 ) n(n<=10^{18}) n(n<=1018)的数中能表示成 m k ( k > 1 ) m^k(k>1) mk(k>1)的数的个数
枚举 n n n和 m m m是不现实的，范围太大， m m m也是根号的级别 所以想一想可不可以枚举 k k k 2 60 2^{60} 260> 1 0 18 10^{18} 1018 所以 k k k最大就是 60 60 60 k k k只有是素数时才对答案有贡献 不然会被容斥减掉 因为如果 m k < = n m^k<=n mk<=n 那么{ x ∣ x k < = n , x < = m x|x^k<=n,x<=m x∣xk<=n,x<=m} 满足 m k m^k mk的数中，若 k k k不是素数 则 m k m^k mk可以等于 ( m b ) p (m^b)^p (mb)p b ∗ p = k b*p=k b∗p=k且 p p p为素数 即满足题意的数都可以表示成 m p m^p mp， p p p是素数 所以我们只需累计 k k k是素数时对答案的贡献 它对答案的贡献就是 n 1 k n^{\frac{1}{k}} nk1，因为 p k = n p^k=n pk=n 但这样会有些重复，如 ( 2 3 ) 4 (2^3)^4 (23)4和 ( 2 4 ) 3 (2^4)^3 (24)3 这个满足容斥，就是加加减减的那个公式
做法就是预处理出60以内的素数再算贡献再容斥
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <complex> #include <algorithm> #include <climits> #include <queue> #include <map> #include <set> #include <vector> #include <iomanip> #define A 1000010 #define B 2010 using namespace std; typedef long long ll; ll pri[17] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59}; ll n; ll calc(ll a) { return pow(n, 1.0 / a) - 1; } int main(int argc, char const *argv[]) { while (cin >> n) { ll c1 = 0, c2 = 0, c3 = 0; for (int i = 0; i < 17; i++) c1 += calc(pri[i]); for (int i = 0; i < 17; i++) for (int j = i + 1; j < 17; j++) c2 += calc(pri[i] * pri[j]); for (int i = 0; i < 17; i++) for (int j = i + 1; j < 17; j++) for (int k = j + 1; k < 17; k++) c3 += calc(pri[i] * pri[j] * pri[k]); cout << c1 - c2 + c3 + 1 << endl; } }