ZROJ 1267 我要打数论
这个题目来源是一个同学开麦对线，说我要打麻将我要打扑克
应clb要求题目不能直接放出来，但是真的感觉太棒了学到许多所以总结一下
分析一波，取min可以转化
[sum^n_{i=1}sum^n_{j=1}min(n,lcm(i,j)+gcd(i,j))
]
[=sum_k^nsum^n_{i=1}sum^n_{j=1}[kleq lcm(i,j)+gcd(i,j)]
]
这是一种常见的min转换方法（我并不知道
继续转化，
[=sum_k^n n^2-sum^n_{i=1}sum^n_{j=1}[k> lcm(i,j)+gcd(i,j)]
]
[=sum_k^n n^2-sum^{k}_{i=1}sum^{k}_{j=1}[k> lcm(i,j)+gcd(i,j)]
]
大于有更好的性质，后面的式子上界为k-1，后面就只和k有关了，令其为(F(n))，即
[F(n)=sum_isum_j [n>lcm(i,j)+gcd(i,j)]
]
考虑一个差分，(G(n)=F(n+1)-F(n))，小于n+1又大于等于n，只能等于n
[G(n)=sum_isum_j [lcm(i,j)+gcd(i,j)=n]
]
考虑枚举(d=gcd(i,j))
[=sum_g^n sum_i^{leftlfloorfrac{n}{g}
ight
floor}sum_j^{leftlfloorfrac{n}{g}
ight
floor}[ijg+g=n][gcd(i,j)=1]
]
因为(n=ijg+g)，则有解的话(g|n)，所以
[=sum_{g|n} sum_i^{leftlfloorfrac{n}{g}
ight
floor}sum_j^{leftlfloorfrac{n}{g}
ight
floor}[ijg+g=n][gcd(i,j)=1]
]
其中(ijg+g=n)，则 (i=frac{frac{n}{g}-1} j) ，枚举i，式子就变成了
[=sum_{g|n} sum_{i|frac{n}{g}-1}[gcd(i,frac{frac{n}{g}-1} i)=1]
]
发现式子只和(frac n g -1)有关了，则令(H(n)=sum_{i|n} [gcd(i,n/i)=1]) （禁止套娃！
这个东西就等于(2^{w(n)})，因为每种因子都要取完，就可以当成01分析
然后就做完了。。。总复杂度(O(T+nlog n))
代码就不贴了