https://www.luogu.com.cn/problem/P1587
神仙题...
首先我们只要考虑所有最简分数就好了，也就是((a,b)=1)的(frac{a}{b})
然后答案就是
(sumlimits_{i=1}^n sumlimits_{j=1}^m [gcd(i,j)=1)且(frac{i}{j})在(k)进制下是纯循环小数(])
（下面令({ x})表示(x)的小数部分）
考虑一个最简分数(frac{x}{y})，它的小数部分({ x/y})显然是((x mod y)/y)
注意到(k)进制下将一个数左移一位相当于乘一个(k)，设分数(x/y)循环节的长度为(r)，那么必然有
(k^r x mod y = x mod y)
由于((x,y)=1)，两边同时乘一个(x^{-1})可得
(k^r equiv 1 pmod y)
也就是存在整数(r,q)（(r>0)），满足(k^r - qy=1)
即((k^r,y)=1)，发现这个成立当且仅当((k,y)=1)。
然后就可以推柿子辣
看后面那个(j)，貌似不太好推了...
但注意到(gcd(jd,k)=1)等价于(gcd(j,k)=1)且(gcd(d,k)=1)，所以
还是不太好做...但不要放弃梦想...
令(f(n)=sum_{i=1}^n [gcd(i,k)=1])
(g(n,k)=sum_{i=1}^n mu(i)[gcd(i,k)=1])（这里为什么是(n,k)？往下看呗...）
如果能快速搞出这两个东西我们就能数论分块了...
先来看(f(n))
考虑两个数互质(a,b)，写成带余除法的形式(a=bq+r)
由于(a,b)互质，所以(r,b)也必须互质（不然直接提个公因子出来，与((a,b)=1)矛盾）。
所以((a,b)=1)等价于((a mod b,b)=1)，那么(f)也很显然啦，每(k)个数是一个循环，所以
(f(n)=lfloorfrac{n}{k} floor f(k) + f(n mod k))
暴力算出(f(0...k))即可
然后是(g(n,k))
中间又有个(gcd)？我们推一波柿子
后面有个(id)...然后又不会了...
注意到(mu)是一个积性函数对于(gcd(a,b)=1)，有(mu(ab)=mu(a)mu(b))，如果(a,b)不互质呢，根据莫比乌斯函数的定义，显然(mu(ab)=0)
于是
你看看后面那一坨...
不就是(g(lfloorfrac{n}{d} floor,d))嘛！
没想到吧...
然后(g(n,k)=sum_{dmid k} mu(d)^2 g(lfloor n/d floor,d))
边界情况就是(g(n,1)=sum_{i=1}^n mu(i))，这种直接杜教筛就好了
然后就做完了...
复杂度不会算...
被卡的话算(g)的时候注意特判一下(mu(d)=0)就不用递归了
跑的贼慢的(Code): https://paste.ubuntu.com/p/GhbXXnVXmJ/