退役了只有一直没怎么做题，感觉水平退步了不少，以前一些比较显然的思路现在可能都想不到了. 这样下去肯定是不行的，我尽量时不时做点水题写点题解恢复一点智商吧.

题意

给定$n,m$，求有多少对$(i,j)$满足$1\le i\le n,1\le j\le m$且$\gcd(i,j)$为素数.

共$T$组数据.

$n\le 10^7,T\le 10^4$

AFO有段时间了，感觉自己什么都不会了，随便研究点东西证明我还活着……

好久没写博客了，随便扔点东西上来除个草.

其实也说不上是黑科技，就是自己平时折腾linux，折腾vim之类的东西的时候发现的一些小技巧罢了.

退役之后一直有点消沉，没有写退役记什么的，最近想了想还是多少放点东西上来.

分治fft是非常明显的做法，不过这样是$\mathcal O(n\log^2n)$的. 把生成函数弄出来之后会发现它是个微分方程，可以有一些神奇的方法来解，具体可以看UR3的题解.

这种求某个东西在最后一个的概率之类的其实可以考虑容斥，设钦定一个集合$S$在它后面的概率为$f(S)$，那么最后的答案为$\sum (-1)^{|S|}f(S)$.

学到了一个新的技巧，树形的依赖关系，把顺序翻转，就可以在依赖父亲和依赖子树之间相互转化.

前置技能：DAG的最小路径覆盖和最小链覆盖.

NOI前的垂死挣扎.

又写了一遍，tarjan真的容易写错……