题目大意：

　　定义函数$f(m)=\displaystyle\sum_{a=0}^{m-1}\sum_{b=0}^{m-1}[m\nmid ab]$，$g(n)=\displaystyle\sum_{m\mid n}f(m)$。

　　共有$q(q\leq2\times10^4)$次询问，每次询问$g(n)(n\leq10^9)$的值。

思路：

　　对$n$分解质因数，得$n=\displaystyle\prod_{i=1}^rp_i^{q_i}$。

　　推公式得$g(n)=\displaystyle\prod_{i=1}^r\frac{(p_i^{q_i+1})-1}{p_i^2-1}-n\prod_{i=1}^r(q_i+1)$。

　　先预处理出质数表，然后暴力分解质因数即可。

1 #include
     
       2 #include
      
        3 typedef unsigned long long qword; 4 typedef unsigned __int128 oword; 5 inline int getint() { 6     register char ch; 7     while(!isdigit(ch=getchar())); 8     register int x=ch^'0'; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10     return x;11 }12 const int M=31628,SIZE=3403;13 bool b[M];14 int p[SIZE];15 inline void init() {16     for(register int i=2;i