P1587 [NOI2016]循环之美 杜教筛
P1587 [NOI2016]循环之美
题目大意：
给定n，m，k。求(K)进制下既约分数(displaystyle frac{x}{y}（1leq xleq n, 1leq yleq m）)且为纯循环小数的个数。
题解：
首先是判断分数(displaystyle frac{x}{y})是否为纯循环小数的方法，
根据打表可以得到结论：
(K)进制下，(displaystyle frac{x}{y})为纯循环小数当且仅当(y)与(k)互质。
证明：
(K)进制下，(displaystyle frac{x}{y})为纯循环小数，则有
[x*k^lequiv x(mod y)(l
eq 0)
]
两边同除(x).
[k^lequiv1(mod y)
]
得(k, y)互质。
证毕。
题目转化为求
[displaystyle sum_{x=1}^{n} displaystyle sum_{y=1}^{m}[gcd(x, y)==1][gcd(y, k)==1]
]
[displaystyle sum_{x=1}^{n} displaystyle sum_{y=1}^{m}[gcd(y, k)==1][gcd(x, y)==1]
]
更换枚举顺序
[displaystyle sum_{y=1}^{m}[gcd(y, k)==1]displaystyle sum_{x=1}^{n} [gcd(x, y)==1]
]
莫比乌斯反演得
[displaystyle sum_{y=1}^{m}[gcd(y, k)==1]displaystyle sum_{x=1}^{n} displaystyle sum_{d|gcd(x, y)}mu(d)
]
枚举约数(d)得
[displaystyle sum_{d=1}^{n}mu(d) displaystyle sum_{d|x}^{n} displaystyle sum_{d|y}^{m}[gcd(y,k)==1]
]
[displaystyle sum_{d=1}^{n}[gcd(d,k)==1]mu(d) displaystyle sum_{x=1}^{displaystyle displaystyle lfloorfrac{n}{d}displaystyle
floor} displaystyle sum_{y=1}^{displaystyle displaystyle lfloor frac{m}{d}displaystyle
floor}[gcd(y,k)==1]
]
[displaystyle sum_{d=1}^{n}[gcd(d,k)==1]mu(d) displaystyle displaystyle lfloor frac{n}{d} displaystyle
floor displaystyle sum_{y=1}^{displaystyle displaystyle lfloor frac{m}{d}displaystyle
floor}[gcd(y,k)==1]
]
令(f(x)=displaystyle sum_{i=1}^{x}[gcd(i,k)==1],s(x,k)=displaystyle sum_{i=1}^{x}[gcd(i,k)==1]mu(i)).
考虑求(f(x))，若(i)与(k)互质，则有(i+k)与(k)互质。
所以
[f(x)=displaystyle lfloordisplaystylefrac{x}{k}displaystyle
floor f(k) + f(x mbox{%} k)
]
预处理(f(x))满足(1leq xleq k)的(f(x)),剩下的递归处理即可。
考虑求(s(x, k)).
[s(x,k)=sum_{i=1}^{x}[gcd(i,k)==1]mu(i)\=sum_{i=1}^{x}mu(i)[gcd(i,k)==1]\=sum_{i=1}^{x}mu(i)sum_{d|gcd(i,k)}mu(d)\=sum_{i=1}^{x}mu(i)sum_{d|i,d|k}mu(d)\=sum_{d|k}mu(d)sum_{d|i}mu(i)\=sum_{d|k}mu(d)sum_{i=1}^{lfloorfrac{x}{d}
floor}mu(i*d)
]
若(gcd(i,d) eq 1)时，(mu(i*d)=0)，对答案没有贡献.
由积性函数的性质(f(ab)=f(a)*f(b))得
[=sum_{d|k}mu(d)sum_{i=1}^{lfloor frac{x}{d}
floor}[gcd(i,d)==1]mu(i)mu(d)\=sum_{d|k}mu(d)^2sum_{i=1}^{lfloor frac{x}{d}
floor}[gcd(i,d)==1]mu(i)\=sum_{d|k}mu(d)^2sum_{i=1}^{lfloor frac{x}{d}
floor}[gcd(i,d)==1]mu(i)\=sum_{d|k}mu(d)^2*s(lfloor frac{x}{d}
floor,d)
]
递归处理即可。
但当(k=1)时，(s(x,k))的值无法通过递归得出。
考虑(k=1)的情况，
[s(x,1)=sum_{i=1}^{x}[gcd(i,1)==1]mu(i)\=sum_{i=1}^{x}mu(i)
]
由于(1leq xleq 1e8)，杜教筛求前缀和即可。
题目中所求的
[ans=displaystyle sum_{d=1}^{n}[gcd(d,k)==1]mu(d) displaystyle displaystyle lfloor frac{n}{d} displaystyle
floor displaystyle sum_{y=1}^{displaystyle displaystyle lfloor frac{m}{d}displaystyle
floor}[gcd(y,k)==1]
]
数论分块处理。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int read() {
int x = 0, f = 1; char ch;
while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
return x * f;
}
map <pair <int, int>, int> mp;
int n, m, K, ans;
int tot, gcd_k[N], f[N], mu[N], Smu[N], vis[N], pri[N];
void init() {
for(int i = 1; i <= K; ++ i) gcd_k[i] = __gcd(i, K) == 1;
for(int i = 1; i <= K; ++ i) f[i] = f[i - 1] + gcd_k[i];
mu[1] = 1;
for(int i = 2; i < N; ++ i) {
if(! vis[i]) pri[++ tot] = i, mu[i] = -1;
for(int j = 1; j <= tot && i * pri[j] < N; ++ j) {
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
mu[i * pri[j]] = - mu[i];
}
}
for(int i = 1; i < N; ++ i) Smu[i] = Smu[i - 1] + mu[i];
}
int Sf(int x) {
return (x / K) * f[K] + f[x % K];
}
int Ss(int x, int k){
if((k == 1 && x <= N) || x == 0) return Smu[x];
if(mp[make_pair(x, k)]) return mp[make_pair(x, k)];
int res = 0;
if(k == 1) {
res = 1;
for(int i = 2, j; i <= x; i = j + 1) {
j = x / (x / i);
res -= (j - i + 1) * Ss(x / i, k);
}
}
else {
for(int i = 1; i * i <= k; ++ i) {
if(k % i) continue;
if(mu[i]) res += Ss(x / i, i);
if(i * i != k && mu[k / i]) {
res += Ss(x / (k / i), k / i);
}
}
}
return mp[make_pair(x, k)] = res;
}
signed main() {
n = read(); m = read(); K = read();
init();
for(int i = 1, j, nw = 0, lst = 0; i <= min(n, m); i = j + 1) {
j = min(n / (n / i), m / (m / i));
nw = Ss(j, K);
ans = ans + (nw - lst) * (n / i) * Sf(m / i);
lst = nw;
}
printf("%lld
", ans);
return 0;
}