原题链接

考察:容斥原理

思路:

       很容易想到筛质数,然后枚举质数2^k 3^k 5^k ...但是如果从指数的取值范围考虑,最小是2,那么最大取到10⁹ 这样必定会TLE.

       换个思路,如果从指数方面考虑,x² x³ x⁵ .那么1~N中,最多有N^1/k 个^k√ N 个取到k次方的数.因为2⁶⁰ > 1e18.所以只需要质数只需要筛到到60.但是要注意的是可能会有重复比如1,所以需要用容斥原理.但这样还需要一个优化:如果指数的乘积>60,我们必须break跳出

这道题真的很玄学,我代码的输出和样例全都差1,结果ans-1就过了...

网上很多题解涉及在pow-1.这是考虑去掉1的情况,最后+1是将答案的1加回来

关于本题温故知识点:

       pow(n,1.0/2)//表示1~n中有多少平方数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N = 100;
 7 const double eps = 1e-6;
 8 int prime[N],cnt;
 9 bool st[N];
10 void GetPrime(int n)
11 {
12     for(int i=2;i<=n;i++)
13     {
14         if(!st[i]) prime[cnt++] = i;
15         for(int j=0;prime[j]<=n/i;j++)
16         {
17             st[i*prime[j]] = 1;
18             if(i%prime[j]==0) break;
19         }
20     }
21 }
22 int main()
23 {
24     ll n;
25     GetPrime(64);
26     while(scanf("%lld",&n)!=EOF)
27     {
28         ll ans = 0;
29         for(int i=1;i<1<<cnt;i++)
30         {
31             int k = 0; ll res = 1;
32             for(int j=0;j<cnt;j++)
33             {
34                 if(i>>j&1)
35                 {
36                     if(res*prime[j]>=60)
37                     {
38                         res = -1;
39                         break;
40                     }
41                     k++,res*=prime[j];
42                 }
43             }
44             if(res!=-1)
45             {
46                 if(k&1) ans+=(ll)(pow(n,1.0/res)+eps);
47                 else ans-=(ll)(pow(n,1.0/res)+eps);
48             }
49         }
50         printf("%lld\n",ans-1);
51     }
52     return 0;
53 }