题面
https://www.luogu.com.cn/problem/P1587
题解
前置知识
题目要求所有(1{leq}x{leq}n,1{leq}y{leq}m)形成的({frac{x}{y}})在k进制下的不同纯循环小数个数。（整数也算）
分析题目，转化条件：纯循环小数相当于((y,k)=1)；而所有值重复的({frac{x}{y}})中，又可以取((x,y)=1)的那个作为代表，这样最好统计。
所以相当于求
({mu(d)})后面的东西已经可以通过数论分块处理了。({sum_{y'=1}^{{lfloor}{frac{m}{d}}{ floor}}}[(y',k)=1])这部分，含义是1~({lfloor}{frac{m}{d}}{ floor})中与k互质的数的个数(f({lfloor}{frac{m}{d}}{ floor}))。由于k小，我们可以预处理(f(1))到(f(k))，然后将({lfloor}{frac{m}{d}}{ floor})分成k的整数倍和除以k后的余数，就可以(O(1))解决这部分。
剩下的东西就是如何解决({sum_{(d,k)=1}^{1{leq}d{leq}R}}{mu(d)})，其中R是数论分块后某一块的右端点。
发现所有的R一定在n或m的整除集合中，所以两次杜教筛就可以解决所有的(summu(R)={sum_{1{leq}d{leq}R}}{mu(d)})。现在的问题是还有一个((d,k)=1)的条件。
我们考虑({sum_{(d,k){ eq}1}^{1{leq}d{leq}R}}{mu(d)})是什么。然后，惊喜地发现：由于k小，所以既满足((d,k){ eq}1)，又满足({mu(d){ eq}0})的数其实不是很多。
用(dt(R))来描述这个和。考虑满足上面一行条件的d和k的gcd，这个gcd只能含有k有的素因子，而且每个次数都不能超过1。但是由于(k{leq}2000)，所以k最多只有4个质因子。所以，这样的gcd最多有15个。然后就可以得出关系式：
所有出现在dt后面的下标都是n或m的整除集合中的数，所以计算所有dt的总复杂度是(O(({sqrt{n}}+sqrt{m})w))，其中w是不同gcd的个数，本题中(w{leq}15)。
综上，本题的总时间复杂度为(O(sqrt{n}w+n^{frac{2}{3}}))。
- 本题有多种做法，其他做法见 https://www.luogu.com.cn/problemnew/solution/P1587
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
#define K 2000
#define T 1000000
ll n,m,k,pn;
ll pri[T+5],smu[T+5];
bool isp[T+5];
inline void Eular(){
smu[1] = 1;
for(rg ll i = 2;i <= T;i++)isp[i] = 1;
for(rg ll i = 2;i <= T;i++){
if(isp[i])pri[++pn] = i,smu[i] = -1;
for(rg ll j = 1;i * pri[j] <= T;j++){
isp[i*pri[j]] = 0;
if(i % pri[j])smu[i*pri[j]] = -smu[i];
else{
smu[i*pri[j]] = 0;
break;
}
}
}
for(rg ll i = 2;i <= T;i++)smu[i] += smu[i-1];
}
ll f[K+5]; //f[i]表示1~i中与k互质的数的个数
inline ll gcd(ll a,ll b){
return b ? gcd(b,a % b) : a;
}
inline ll calc(ll n){ //计算1~i中与k互质的数的个数
return (n / k) * f[k] + f[n%k];
}
unordered_map<ll,ll>Hash;
inline ll summu(int n){ //杜教筛
if(n <= T)return smu[n];
if(Hash.count(n))return Hash[n];
ll ans = 1;
int L,R = 1;
while(R < n){
L = R + 1,R = n / (n / L);
ans -= 1ll * (R - L + 1) * summu(n / L);
}
return Hash[n] = ans;
}
vector<ll>fac;
ll fn,fc[16+5]; //所有k的mu值不等于0的约数(除了1)
inline void divide(ll n){ //分解k
for(rg ll i = 1;i <= pn;i++){
if(n % pri[i] == 0){
fac.push_back(pri[i]);
while(n % pri[i] == 0)n /= pri[i];
}
if(n == 1)break;
}
}
unordered_map<ll,ll>Dt;
inline ll dt(int n){ //1~n中与k互质的数的mu值之和
if(!n)return 0;
if(Dt.count(n))return Dt[n];
ll ans = 0;
for(rg ll i = 1;i <= fn;i++)ans += (smu[fc[i]] - smu[fc[i]-1]) * (summu(n/fc[i]) - dt(n/fc[i]));
return Dt[n] = ans;
}
int main(){
cin >> n >> m >> k;
Eular();
divide(k);
for(rg ll mask = 1;mask < 1ll << fac.size();mask++){
ll cur = 1;
for(rg ll i = 0;i < fac.size();i++)
if((bool)(mask & (1ll << i)))cur *= fac[i];
fc[++fn] = cur;
}
for(rg ll i = 1;i <= k;i++)f[i] = f[i-1] + (gcd(i,k) == 1);
ll ans = 0;
int L,R = 0,limit = min(n,m);
while(R < limit){
L = R + 1,R = min(n / (n/L),m / (m/L));
ans += ((summu(R)-dt(R)) - (summu(L-1)-dt(L-1))) * (n / L) * calc(m / L);
}
cout << ans << endl;
return 0;
}