LOJ2085 [NOI2016]循环之美
题面：LOJ
解析
考虑对于题中所谓纯循环小数(frac{i}{j})，设循环节长度为(a)，有(k^{a}frac{i}{j} equiv frac{i}{j} pmod{j})，即(k^a equiv 1 pmod{j})，也就是(k^a)与(j)互质，即(k)与(j)互质，而数值要求两两不同，那么(i)与(j)互质即可，所以我们要求的式子即为：
变一下形：
又([jd ot k])即为([j ot k][d ot k])，所以上式即为：
考虑右边的那个式子如何计算，设(G(i)=sum_{j=1}^{i} [j ot k])，那么有：
因为(k)很小，所以预处理即可(O(1))计算。
那么现在有一个做法：直接上数论分块，暴力预处理$ mu(d) [d ot k]$的前缀和，这样你可以得84分。
考虑优化，设(S(i,j)=sum_{t=1}^{i} mu(d) [d ot j])，对于(j)，我们考虑它的某一个质因子(p)，那么(j)一定能表示成(p^c q(p ot q))的形式，而([d ot j])就可以表示成([d ot p][d ot q])，现在考虑如何计算满足条件的数，我们先计算([d ot q])的数，再从中减去(d)不与(p)互质的即可。与(q)互质的数一定可以表示为(p^c y(p ot y))，而当(c=0)时，(y)与(p)互质，不必减去，而(c>1)时，(mu(p^c y)=0)，没有贡献。因此，减去的部分只需考虑(py)即可，那么有：
又因为当(p ot y)时，(mu(py)=mu(p) mu(y)),所以上式又可以表示为：
观察到(mu(p)=-1)，([y ot p][y ot q]=[y ot j])，所以又有：
那么有：
记忆化即可递归计算，边界条件是：
当(i=0)时，(S(i,j)=0)；当(j=1)时，(S(i,j)=sum_{t=1}^{i} mu(t))，杜教筛计算即可。
代码
#include<map>
#include<cstdio>
#define LL long long
using namespace std;
inline int In(){
char c=getchar(); int x=0,ft=1;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') ft=-1;
for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
return x*ft;
}
const int lim=5000000;
int n,m,K;
int p[500005],p_cnt=0; bool vis[lim+5];
int mu[lim+5],f[2005],cp[lim+5],cq[2005]; LL ans=0;
inline int min(int a,int b){ return a<b?a:b; }
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }
inline LL F(int x){ return (x/K)*f[K]+f[x%K]; }
inline void Get_mu(){
mu[1]=1;
for(int i=2;i<=lim;++i){
if(!vis[i]){ p[++p_cnt]=i; mu[i]=-1;cp[i]=i; }
for(int j=1;j<=p_cnt;++j){
if(i*p[j]>lim) break;
vis[i*p[j]]=1;
cp[i*p[j]]=p[j];
if(i%p[j]==0) break;
else mu[i*p[j]]=-mu[i];
}
}
for(int i=1;i<=lim;++i) mu[i]+=mu[i-1];
}
inline void Get_f(){
for(int i=1;i<=K;++i)
f[i]=f[i-1]+(gcd(i,K)==1);
}
inline void Get_q(){
for(int i=2;i<=K;++i){
cq[i]=i;
while(cq[i]%cp[i]==0) cq[i]/=cp[i];
}
}
map<int,LL> mp,mp2[2005];
inline LL Sum(int x){
if(x<=lim) return mu[x];
else if(mp.count(x)) return mp[x];
LL ans=0;
for(int l=2,r;l<=x;l=r+1){
r=x/(x/l);
ans+=1ll*(r-l+1)*Sum(x/l);
}
return mp[x]=1-ans;
}
inline LL S(int n,int k){
if(n==0) return 0;
if(k==1) return Sum(n);
if(mp2[k].count(n)) return mp2[k][n];
return mp2[k][n]=S(n,cq[k])+S(n/cp[k],k);
}
int main(){
n=In(); m=In(); K=In();
Get_mu(); Get_f(); Get_q();
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
if(m/l) r=min(r,m/(m/l));
ans+=1ll*(S(r,K)-S(l-1,K))*(n/l)*F(m/l);
}
printf("%lld
",ans);
fclose(stdin); fclose(stdout);
return 0;
}