循环之美
求 ∑ x = 1 n ∑ y = 1 m x y \sum\limits_{x=1}^n\sum\limits_{y=1}^m\frac{x}{y} x=1∑ny=1∑myx 在 k k k 进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数。
先思考怎么转换。
首先肯定满足 gcd ( x , y ) = 1 \gcd(x,y)=1 gcd(x,y)=1。
假设
x
y
\frac{x}{y}
yx 的循环节长度为
l
l
l，根据在
k
k
k 进制下的数乘以
k
p
k^p
kp 相当于将小数点往后挪
p
p
p 位，那么有：
{
x
k
l
y
}
=
{
x
y
}
\{\frac{xk^l}{y}\}=\{\frac{x}{y}\}
{yxkl}={yx}
转换一下上面那个式子，有：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \frac{xk^l}{y}…
那么题意就可以转换为求：
∑
i
=
1
n
∑
j
=
1
m
[
gcd
(
i
,
j
)
=
1
]
[
gcd
(
j
,
k
)
=
1
]
\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1][\gcd(j,k)=1]
i=1∑nj=1∑m[gcd(i,j)=1][gcd(j,k)=1]
先化简原式，有：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ &\sum_{i=1}^{n…
再设个函数，并化简：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ f(n)=\sum_{i=1…
思考，当
i
>
k
i>k
i>k 时，有
gcd
(
i
,
k
)
=
gcd
(
i
+
k
,
k
)
\gcd(i,k)=\gcd(i+k,k)
gcd(i,k)=gcd(i+k,k)，那么答案肯定是呈现一个长度为
k
k
k 的循环，那么有：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ f(n) &=f(n \bm…
那么原式等于：
∑
p
=
1
min
(
n
,
m
)
⌊
n
d
⌋
f
(
⌊
m
p
⌋
)
μ
(
p
)
[
gcd
(
p
,
k
)
=
1
]
\sum_{p=1}^{\min(n,m)}\lfloor\frac{n}{d}\rfloor f(\lfloor\frac{m}{p}\rfloor)\mu(p)[\gcd(p,k)=1]
p=1∑min(n,m)⌊dn⌋f(⌊pm⌋)μ(p)[gcd(p,k)=1]
现在已经有整除分块了，然后是处理
∑
i
=
1
n
μ
(
i
)
[
gcd
(
i
,
k
)
=
1
]
\sum\limits_{i=1}^{n}\mu(i)[\gcd(i,k)=1]
i=1∑nμ(i)[gcd(i,k)=1] 前缀和的问题。
法一
设前面那个式子为 s ( n , k ) s(n,k) s(n,k)。
尝试化简
s
(
n
,
k
)
s(n,k)
s(n,k)，则有：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ s(n,k)&=\sum_{…
然后数论分块即可。
法二
这里是设前面那个式子为 s ( n ) s(n) s(n)，则有：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ s(n)&=\sum_{i=…
先看前面那个：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ &\sum_{i=1}^{n…
那么最终有：
s
(
n
)
=
1
−
∑
i
=
2
n
[
gcd
(
i
,
k
)
=
1
]
s
(
⌊
n
i
⌋
)
s(n)=1-\sum_{i=2}^{n}[\gcd(i,k)=1]s(\lfloor\frac{n}{i}\rfloor)
s(n)=1−i=2∑n[gcd(i,k)=1]s(⌊in⌋)
数论分块即可。
#include <bits/stdc++.h>
using namespace std;
const int _ = 1e6 + 5;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n, m, k;
int g[2007], A[_];
int cnt, vis[_], pri[_], mu[_];
map<int, int> ans_A;
long long ans;
int f(int n)
{
return g[n % k] + (n / k) * g[k];
}
void init()
{
for(int i = 1; i <= k; ++i) g[i] = g[i - 1] + (__gcd(i, k) == 1);
mu[1] = A[1] = 1;
for(int i = 2; i <= _ - 5; ++i)
{
if(!vis[i])
{
mu[i] = -1;
pri[++cnt] = i;
}
for(int j = 1; j <= cnt && i * pri[j] <= _ - 5; ++j)
{
int p = i * pri[j];
vis[p] = 1;
if(i % pri[j] == 0) break;
mu[p] = -mu[i];
}
A[i] = A[i - 1] + mu[i] * (f(i) - f(i - 1));
}
}
int F(int x)
{
if(x <= _ - 5) return A[x];
if(ans_A.find(x) != ans_A.end()) return ans_A[x];
int ans = 1;
for(int l = 2, r; l <= x; l = r + 1)
{
r = x / (x / l);
ans -= F(x / l) * (f(r) - f(l - 1));
}
return ans_A[x] = ans;
}
signed main()
{
n = read(), m = read(), k = read();
init();
for(int l = 1, r; l <= min(n, m); l = r + 1)
{
r = min(n / (n / l), m / (m / l));
ans += 1LL * (n / l) * f(m / l) * (F(r) - F(l - 1));
}
printf("%lld\n", ans);
return 0;
}