计蒜客 30999.Sum-筛无平方因数的数 (ACM-ICPC 2018 南京赛区网络预赛 J)

26.87%
1000ms
512000K

A square-free integer is an integer which is indivisible by any square number except $2^2 cdot 312=22⋅3 is not, because 2^222 is a square number. Some integers could be decomposed into product of two square-free integers, there may be more than one decomposition ways. For example, 6 = 1cdot 6=6 cdot 1=2cdot 3=3cdot 2, n=ab6=1⋅6=6⋅1=2⋅3=3⋅2,n=ab and n=ban=ba are considered different if a ot = ba̸=b. f(n)f(n) is the number of decomposition ways that n=abn=ab such that aa and bb are square-free integers. The problem is calculating sum_{i = 1}^nf(i)∑i=1nf(i).$

Input

The first line contains an integer

For each test case, there first line has a integer $10^7)n(n≤2⋅107).$

Output

For each test case, print the answer $sum_{i = 1}^n f(i)∑i=1nf(i).$

Hint

$sum_{i = 1}^8 f(i)=f(1)+ cdots +f(8)∑i=18f(i)=f(1)+⋯+f(8)=1+2+2+1+2+4+2+0=14=1+2+2+1+2+4+2+0=14.$

样例输入

2
5
8

样例输出

8
14

题目来源

ACM-ICPC 2018 南京赛区网络预赛

题意很好理解，就是求1-n中没有平方因数的数的个数。首先预处理出来，然后就直接输出就可以了。

类似欧拉函数筛素数，在筛素数的时候把平方因数筛掉就可以了。

代码:

 1 //J-筛无平方因数的数
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<bitset>
 7 #include<cassert>
 8 #include<cctype>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 using namespace std;
21 typedef long long ll;
22 
23 const double PI=acos(-1.0);
24 const double eps=1e-6;
25 const ll mod=1e9+7;
26 const int inf=0x3f3f3f3f;
27 const int maxn=2e7+10;
28 const int maxm=100+10;
29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
30 
31 bool is_prime[maxn];
32 int prime[maxn];
33 ll f[maxn],ans[maxn];
34 int h;
35 
36 void init(int n)
37 {
38     f[1]=1;
39     for(int i=2;i<n;i++){
40         if(!is_prime[i]){
41             prime[++h]=i;
42             f[i]=2;
43         }
44         for(int j=1;j<=h&&i*prime[j]<n;j++){
45             is_prime[i*prime[j]]=1;
46             if(i%prime[j]==0){
47                 if(i%(prime[j]*prime[j])==0) 
48                     f[i*prime[j]]=0;
49                 else 
50                     f[i*prime[j]]=f[i]/2;
51                 break;
52             }
53             else{
54                 f[i*prime[j]]=f[i]*2;
55             }
56         }
57     }
58     for(int i=1;i<maxn;i++)
59         ans[i]=ans[i-1]+f[i];
60 }
61 
62 int main()
63 {
64     h=0;
65     init(maxn);
66     int t;
67     scanf("%d",&t);
68     while(t--){
69         int n;
70         scanf("%d",&n);
71         printf("%lld
",ans[n]);
72     }
73     return 0;
74 }

溜了。。。