日常诈骗签到题

不管你认不认识竭泽，都给你重新介绍一下

竭泽，当代水平最底层的退役acmer，擅长出毒瘤题面签到题恶心选手，十恶不赦，大逆不道

可以给大家体会体会

题面十分吓人的诈骗签到题

无法分清是HI还是HL的毒瘤签到题

所以，当云哥邀请竭泽的时候，竭泽心里当然是打起了小算盘，开始整活，再出一个题面恶心的签到题

题目：

竭泽十分喜欢数论，并且在莫比乌斯反演点了很多奇怪的技能点

在介绍这个问题之前，竭泽会给大家介绍一点数论常识常见的数论符号和数论解题trick

0. gcd(i, j)表示i和j的最大公因数
1. [n == 1] 这个符号表示，若n == 1，则返回1，否则返回0
2. $\mu$ (i)是莫比乌斯函数，

, 其中 $p_i$ 为质因数

3. 狄利克雷卷积我们定义 * 为狄利克雷卷积符号，那么 $h(n) = (f * g)(n) = \sum_{d|n} f(d)g(\frac{n}{d})$
4. 莫比乌斯反演

其中有一个重要性质

$\sum_{d|n} \mu(d) = [n==1]$

这里给出莫比乌斯线性筛的函数

const int maxn=1e6+5; bool vis[maxn]; int prime[maxn],mu[maxn]; void init_mu(int n){//init_mu(n) 就可得到1-n的莫比乌斯函数的值，存在mu中     int cnt=0;     mu[1]=1;     for(int i=2;i<n;i++){         if(!vis[i]){             prime[cnt++]=i;             mu[i]=-1;         }         for(int j=0;j<cnt&&i*prime[j]<n;j++){             vis[i*prime[j]]=1;             if(i%prime[j]==0)   {mu[i*prime[j]]=0;break;}             else { mu[i*prime[j]]=-mu[i];}         }     } }

使用这个函数之后 $\mu (i) = mu[i]$ ，可以用这个函数存放莫比乌斯函数的值

因为以前老是有例题，这次就不放例题了

竭泽这里有T个问题，请你快问快答，检测一下你到底学了多少东西

给你一个数n，问
$\sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{d=1}^{j} \lfloor \frac{n}{i} \rfloor \cdot \mu(d) \cdot[d \mid i][d \mid j]$
的结果

详情