[bzoj4652]循环之美

对于一个分数x/y（x和y互素），在k进制下为纯循环当且仅当y和k互素
证明：任意一个分数都可以写成0.abbbbbbbb的形式（不妨假设a尽量短），设a的位数为l1，b的位数为l2，那么原分数即$\frac {b-a}{(k^{l2}-1)*k^{l1}}$
必要性：当l1=0的时候分母与k互素，即纯循环推出了y与k互素
充分性：反证法，设存在使得$l1>0$且$k^{l1}|b-a$，那么必然有$k|b-a$，也就是b和a的最后一位相同，那么可以将a的最后一位与b的前l2-1位组成新的循环节，与a最短的假设不成立
考虑如何计算：$\sum_{1\le i\le m}[(i,k)==1]\sum_{1\le j \le n}[(i,j)==1]$
先对后半部分莫反并提到前面，即$\sum_{t=1}^{m}[(t,k)==1]*(n/t)*\mu(t)\sum_{i=1}^{m/t}[(i,k)==1]$
考虑对于最后一个式子，设$f(n)=\sum_{i=1}^{n}[(i,k)==1]$，可以用$f(i)=(i/k)*f(k)+f(i\ mod\ k)$来求（预处理前k个值）
对其数论分块，即$\sum_{m/t,n/t}f(m/t)*(n/t)\sum_{t=l}^{r}[(t,k)==1]*\mu(t)$
再令$g(n,k)=\sum_{i=1}^{n}[(i,k)==1]*\mu(i)$，考虑快速递推计算g
对于k的任意质因子p，设$k=p^{t}*q$（p和q互素），那么$[(i,k)==1]=[(i,q)==1]-[(i,q)==1]*[p|i]$
把这个代入原式，即$g(n,k)=g(n,q)-\sum_{i=1}^{n/p}[(i,q)==1]*\mu(ip)$
由于当i与p不互素时$\mu(ip)=0$，因此添加条件$(i,p)=1$，$原式=g(n,q)-\sum_{i=1}^{n/p}[(i,q)==1]*[(i,p)==1]*\mu(i)*\mu(p)$
对该式化简（提出$\mu(p)=-1$，i与q和p都互素等价于(i,qp)=1），最终就得到$g(n,k)=g(n,q)+g(n/p,k)$
考虑递归，由于第一维和第二维的取值都只有$\sqrt{n}$和$\sqrt{k}$种，存下来即可（第一维用hash），递归边界条件为：1.当$n=0$时结果为0；2.当$k=1$时结果为莫比乌斯函数的前缀和，杜教筛即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define ll long long

 4 #define N 10000005

 5 map<int,int>id;

 6 map<int,int>sum;

 7 int V,n,m,k,f[2005],a[11],vis[N],p[N],mu[N];

 8 ll ans,g[N/10][11];

 9 int gcd(int x,int y){

10     if (!y)return x;

11     return gcd(y,x%y);

12 }

13 void pre(){

14     mu[1]=1;

15     for(int i=2;i<N-4;i++){

16         if (!vis[i]){

17             p[++p[0]]=i;

18             mu[i]=-1;

19         }

20         for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){

21             vis[i*p[j]]=1;

22             if (i%p[j]==0){

23                 mu[i*p[j]]=0;

24                 break;

25             }

26             mu[i*p[j]]=-mu[i];

27         }

28     }

29     for(int i=1;i<N-4;i++)mu[i]+=mu[i-1];

30     for(int i=1;i<=k;i++)f[i]=f[i-1]+(gcd(i,k)==1);

31     for(int i=1;i<=p[0];i++)

32         if (k%p[i]==0)a[++a[0]]=p[i];

33 }

34 int calc_f(int t){

35     return f[k]*(t/k)+f[t%k];

36 }

37 int djs(int k){

38     if (k<N-4)return mu[k];

39     if (sum[k])return sum[k];

40     int ans=1;

41     for(int i=2,j;i<=k;i=j+1){

42         j=k/(k/i);

43         ans-=(j-i+1)*djs(k/i);

44     }

45     return sum[k]=ans;

46 }

47 ll calc_g(int n,int p){

48     if ((n<2)||(!p))return djs(n);

49     if (!id[n])id[n]=++V;

50     int x=id[n];

51     if (g[x][p])return g[x][p];

52     return g[x][p]=calc_g(n,p-1)+calc_g(n/a[p],p);

53 }

54 int main(){

55     scanf("%d%d%d",&n,&m,&k);

56     pre();

57     for(int i=1,j;i<=min(n,m);i=j+1){

58         j=min(n/(n/i),m/(m/i));

59         ans+=(calc_g(j,a[0])-calc_g(i-1,a[0]))*calc_f(m/i)*(n/i);

60     }

61     printf("%lld",ans);

62 }

巴特西

[bzoj4652]循环之美

最新文章

热门文章