ACM-ICPC 2018 南京赛区网络预赛 J. Sum

A square-free integer is an integer which is indivisible by any square number except $2^2 * 3,12=2^2*3 is not,$

$2^2 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 = 1* 6, 6=2* 3=3*2 6=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

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 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <string>
 7 #include <deque>
 8 #include <set>
 9 #include <queue>
10 #include <cmath>
11 #define  ll long long 
12 #define  M 20000004
13 #define  P  pair<int,int>
14 using namespace std;
15 bool  vis[M];
16 int sum[M];
17 void  init()
18 {
19     int u=sqrt(M+0.5);
20     for(int i=1;i<=M;i++) vis[i]=1;
21     for(int i=2;i<=u;i++)
22     {
23         int k=i*i;
24         for(int j=k;j<M;j+=k)
25         {
26             if(vis[j])  vis[j]=0;
27         }
28     }
29     /*
30     1 2 3 4 5 6 7 8
31     1 2 3 3 4 5 6 6
32     */
33     for(int i=1;i<M;i++)
34     {
35         if(vis[i]){
36             sum[i]=sum[i-1]+1;
37         }
38         else  sum[i]=sum[i-1];
39     }
40 }
41 int t,n;
42 int  main()
43 {
44     init();
45     scanf("%d",&t);
46     while(t--)
47     {
48         scanf("%d",&n);
49         int u=sqrt(n+0.5);
50         ll ans=0;
51         /*
52         n==8
53         i==1 : 1*8最大是8.
54         (1,2),(1,3),(1,5),(1,6),(1,7) 
55         (2,1),(3,1),(5,1),(6,1),(7,1)
56         (1,1) 
57         那么 2*5+1==11
58         i==2  : 2*4最大是 4
59         (2,3) 
60         (3,2)
61         (2,2)
62         1*2+1==3
63         11+3==14
64         */
65         for(int i=1;i<=u;i++){
66             if(!vis[i])  continue;
67             int y=n/i;
68             ans+=(ll)(sum[y]-sum[i])*2+1;
69         }
70         printf("%lld
",ans);
71     }
72     return 0;
73 }