摘要:欧拉函数表示互质后杜教筛

SP19985 GCDEX2 - GCD Extreme (hard)

题面

题目分析

求:

先来看一个愚蠢的式子:

设$S(n)=\sum_{d=1}^{n}\varphi(d)\lfloor\frac{n}{d}\rfloor^2$且$S(n)=\sum_{i=1}^{n}f(n)$,考虑求出$f(n)$:

发现后面的$(\lfloor\frac{n}{d}\rfloor^2-\lfloor\frac{n-1}{d}\rfloor^2)$只有在$d|n$时会等于$2\cdot\frac{n}{d}-1$,于是就可以写成一个卷积的形式:

这下就可以考虑杜教筛:

由于$f=2\cdot\varphi * id-id$,构造$g=1$:

这个式子是可以根号复杂度预处理的,这样就可以进行杜教筛了.

不过本题数据范围太大,此做法无法通过.

说起来前前后后用了3种方法来做这个式子,但是都忽略了$j\geq i+1$这个条件,因为可以减去相同的数$\gcd$为本身之后除以二获得这个值.

但是考虑进这个条件,回到式子:

枚举约数:

对于每一个相同的$j$来考虑,它仅会被小于它的$i$枚举到,并且如果这两个数互质的话就会被计入$1$的贡献.

于是可以用欧拉函数表示这个过程:

发现可以数论分块,然后用杜教筛来处理欧拉函数的前缀和,令$S(n)=\sum_{i=1}^{n}\varphi(i)$:

根据$\varphi * 1=id$,令$g=1$:

注意一下因为在原先的和式中$j$不可能等于$1$,所以求出欧拉函数前缀和之后需要减去$1$.

题目对$2^{64}$取模,用unsigned long long自然溢出即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "unordered_map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef unsigned long long ulxl;
const ulxl big=37000010;
ulxl T,n;
ulxl phi[big],prime[big],ca[big],vis[big],pre[big];
std::unordered_map<ulxl,ulxl>mem;
inline ulxl read()
{
char c(getchar());
ulxl x(0);
for(;!isdigit(c););
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return x;
}
inline void prework()
{
phi[1]=1;
for(R ulxl i(2);i<big;++i)
{
if(!vis[i])vis[i]=true,phi[i]=i-1,prime[++prime[0]]=i;
for(R ulxl j(1);j<=prime[0];++j)
{
if(i*prime[j]>big)break;
vis[i*prime[j]]=true;
if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
else {phi[i*prime[j]]=phi[i]*prime[j];break;}
}
}
for(R ulxl i(1);i<big;++i)phi[i]=phi[i-1]+phi[i];
}
inline ulxl calc(ulxl x)
{
ulxl ret;
if(x&1ull)ret=1ull*x*((x+1)>>1);
else ret=1ull*(x>>1)*(x+1);
return ret;
}
ulxl SPhi(ulxl x)
{
if(x<big)return phi[x];
if(mem[x])return mem[x];
ulxl ret=calc(x);
for(R ulxl l(2),r;l<=x;l=r+1ull)
{
ulxl de=x/l;
r=x/de;
ulxl mul=SPhi(de);
ret=ret-1ull*mul*(r-l+1ull);
}
return mem[x]=ret;
}
int main(void)
{
prework();
T=read();
while(T--)
{
std::cin>>n;
ulxl ans=0;
for(R ulxl l(1ull),r;l<=n;l=r+1ull)
{
ulxl de=n/l,l_=l-1ull;
r=n/de;
ulxl mul1=calc(r),mul3=calc(l_),mul2=SPhi(de)-1ull;
ans=ans+1ull*mul1*mul2-1ull*mul3*mul2;
}
std::cout<<ans;endl;
}
return 0;
}