题面
Sol
(设x，y且gcd(x, y)=1)若使(frac{x}{y})的(k)进制小数是纯循环小数
则一定存在某次除法中余数在之前出现过
也就是存在(L>0)且(xequiv x*k^L(mod y))
而(x，y互质)那么同时乘上x的逆元则(k^Lequiv1(mod y))
所以(k^L=a*y+1(a in Z))
而(y)与(a*y+1)互质，辗转相除法可证
所以(k^L与y)互质，易得(k与y也互质)
所以我们就证明了伪证当(k与y)互质时，才会出现(frac{x}{y})的(k)进制小数是纯循环小数
接下来就解题辣
暴力求就不讲了
直接推柿子：
要求的就是(sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i, j)==1, gcd(j, k)==1])
莫比乌斯反演一波
如果(sum_{i=1}^{lfloorfrac{m}{d}
floor}[gcd(i, k)==1])可以预处理(O(1))求
那么就有了(O(n))的解法
设(x=lfloorfrac{m}{d}
floor)
如果(x<=k)直接(O(k))处理
否则
因为(gcd(i, k)=gcd(i\%k, k))，所以(O(k))处理后乘上(lfloorfrac{x}{k}
floor)
$O(n)$84分常数很大
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(2e7 + 1);
IL ll Read(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int N, num, prime[_], mu[_], k, f[2010];
bool isprime[_];
IL int Gcd(RG int x, RG int y){ return !y ? x : Gcd(y, x % y); }
IL void Prepare(){
isprime[1] = 1; mu[1] = 1;
for(RG int i = 2; i < N; ++i){
if(!isprime[i]) prime[++num] = i, mu[i] = -1;
for(RG int j = 1; j <= num && i * prime[j] < N; ++j){
isprime[i * prime[j]] = 1;
if(i % prime[j]) mu[i * prime[j]] = -mu[i];
else{ mu[i * prime[j]] = 0; break; }
}
}
for(RG int i = 1; i <= k; ++i) f[i] = f[i - 1] + (Gcd(i, k) == 1);
}
int main(RG int argc, RG char* argv[]){
RG int n = Read(), m = Read(); k = Read();
N = min(m + 1, _); Prepare(); RG ll ans = 0;
for(RG int i = 1; i <= n; ++i){
if(Gcd(i, k) != 1) continue;
RG ll x = m / i, F = f[x % k] + 1LL * (x / k) * f[k];
ans += 1LL * mu[i] * (n / i) * F;
}
printf("%lld
", ans);
return 0;
}
怎么优化？
这玩意儿后面都可以(O(1))求了
又看到(lfloorfrac{n}{d}
floor和lfloorfrac{m}{d}
floor)可以分块
如果能求出(mu(d)[gcd(d, k)==1])的前缀和就好了
那就继续推柿子：
设$$G(n,k)=sum_{d=1}^{n}mu(d)[gcd(d, k)==1]$$
后面的(gcd)和之前推的时候类似，这里是一样的，所以莫比乌斯反演一波得
后面的(sum_{j=1}^{lfloorfrac{n}{i}
floor}mu(i*j))，显然只有当(gcd(i, j)=1)时(mu(i*j))才不为(0)
所以可以写成(sum_{j=1}^{lfloorfrac{n}{i}
floor}mu(i)mu(j)[gcd(i,j)==1])
代入
前面的也可以(O(k))处理出来，(G)貌似可以杜教筛似的递归处理
暴力在筛里搞一搞k的约数
那不就做完了，复杂度不会证明(O(跑的过))
某些OJ的数据太强啦要卡一卡预处理的大小才能过
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(4e6 + 1);
IL ll Read(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int N, num, prime[_], mu[_], k, f[2010], smu[_];
map < pair <int, int> , ll > G;
bool isprime[_];
IL int Gcd(RG int x, RG int y){ return !y ? x : Gcd(y, x % y); }
IL void Sieve(){
isprime[1] = 1; smu[1] = mu[1] = 1;
for(RG int i = 2; i < N; ++i){
if(!isprime[i]) prime[++num] = i, mu[i] = -1;
for(RG int j = 1; j <= num && i * prime[j] < N; ++j){
isprime[i * prime[j]] = 1;
if(i % prime[j]) mu[i * prime[j]] = -mu[i];
else{ mu[i * prime[j]] = 0; break; }
}
smu[i] = smu[i - 1] + mu[i];
}
for(RG int i = 1; i <= k; ++i) f[i] = f[i - 1] + (Gcd(i, k) == 1);
}
IL ll Du_Sieve(RG int n, RG int m){
if(!n) return 0;
if(m == 1 && n < _) return smu[n];
if(G[make_pair(n, m)]) return G[make_pair(n, m)];
RG ll ans = 0;
if(m == 1){
ans = 1;
for(RG int i = 2, j; i <= n; i = j + 1){
j = n / (n / i);
ans -= Du_Sieve(n / i, 1) * (j - i + 1);
}
}
else{
for(RG int i = 1; i * i <= m; ++i){
if(m % i) continue;
if(mu[i] != 0) ans += Du_Sieve(n / i, i);
if(i * i != m && mu[m / i] != 0) ans += Du_Sieve(n / (m / i), m / i);
}
}
return G[make_pair(n, m)] = ans;
}
int main(RG int argc, RG char* argv[]){
RG int n = Read(), m = Read(); k = Read();
N = min(m + 1, _); Sieve(); RG ll ans = 0, nxt, lst = 0;
for(RG int i = 1, j; i <= n; i = j + 1){
j = n / (n / i); if(m / i) j = min(j, m / (m / i));
RG ll x = m / i, F = f[x % k] + 1LL * (x / k) * f[k];
nxt = Du_Sieve(j, k);
ans += 1LL * (nxt - lst) * (n / i) * F;
lst = nxt;
}
printf("%lld
", ans);
return 0;
}