1742 开心的小Q

 1 #include<bits/stdc++.h>
 2 typedef long long LL;
 3 using namespace std;
 4 bool prime[100005];
 5 LL ak[100005];
 6 LL mul[100005];
 7 const int BufferSize=1<<16;
 8 char buffer[BufferSize],*head,*tail;
 9 inline char Getchar() {
10     if(head==tail) {
11         int l=fread(buffer,1,BufferSize,stdin);
12         tail=(head=buffer)+l;
13     }
14     return *head++;
15 }
16 inline int read() {
17     int x=0,f=1;char c=Getchar();
18     for(;!isdigit(c);c=Getchar()) if(c==‘-‘) f=-1;
19     for(;isdigit(c);c=Getchar()) x=x*10+c-‘0‘;
20     return x*f;
21 }
22 LL slove(LL n);
23 int akk[100005];
24 int main(void)
25 {
26     int cn = 0;
27     mul[1] = 1;int ap = 0;
28     for(int i = 2; i <= 100000; i++)
29     {
30         if(!prime[i])
31         {
32             ak[cn++] = i;
33             mul[i] = -1;
34         }
35         for(int j = 0; j < cn&&(LL)ak[j]*i<=100000; j++)
36         {
37             if(i%ak[j])
38             {
39                 prime[i*ak[j]] = true;
40                 mul[i*ak[j]] = -mul[i];
41             }
42             else
43             {
44                 prime[i*ak[j]] = true;
45                 mul[i*ak[j]] = 0;
46                 break;
47             }
48         }
49         if(mul[i])akk[ap++] = i;
50     }
51     LL n,m;
52    n = read(),m=read();
53     LL c = sqrt(n); LL sum = 0;
54     sum = slove(m)-slove(n-1);
55     printf("%lld\n",sum);
56     return 0;
57 }
58 LL slove(LL n)
59 {   if(n == 0)return 0;
60     LL c = sqrt(n);LL sum = 0;
61     for(int i = 2;i <= c;i++)
62     {
63         if(!mul[i])
64         {
65             sum += n/i;
66         }
67     }
68     for(int i = 1;i <= n/c-1;i++)
69     {
70         LL a,b;
71         a = n/(i+1);
72         b = n/i;
73         a++;LL v = 0;
74         for(int j = 0;akk[j] <= sqrt(b);j++)
75         {
76             sum -= (mul[akk[j]]*((b)/(akk[j]*akk[j])-(a-1)/(akk[j]*akk[j])))*i;
77         }
78     }
79     return sum;
80 }