首页 > 其他 > 详细

[NOI2016]循环之美(杜教筛)

时间:2018-08-17 18:43:24      阅读:187      评论:0      收藏:0      [点我收藏+]

首先要求每个数互不相等,故有$x\perp y$。

可以发现$\frac{x}{y}$在$k$进制下为纯循环小数的充要条件为$x\cdot k^{len}\equiv x(mod\ y)$,即$y\perp k$。

接下来进行经典的推导:
$$\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[i\perp j][j\perp k]\\=&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum_{d|i,d|j}\mu(d)[j\perp k]\\=&\sum\limits_{d=1}^{min(n,m)}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[jd\perp k]\\=&\sum\limits_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[j\perp k][d\perp k]\end{aligned}$$

令$f(n)=\sum\limits_{i=1}^{n}[i\perp k]$,由于$gcd(i,k)=gcd(i-k,k)$,故$f(n)=\lfloor\frac{n}{k}\rfloor\cdot f(k)+f(n\%k)$

再令$g(i)=\mu(i)[i\perp k]$,则答案为$\sum\limits_{d=1}^{min(n,m)}g(d)f(\lfloor\frac{m}{d}\rfloor)\lfloor\frac{n}{d}\rfloor$

令$G(n,k)$为$g()$的前缀和,同样进行根号优化:
$$G(n,k)=\sum\limits_{i=1}^{n}\mu(i)[i\perp k]=\sum\limits_{i=1}^{n}\mu(i)\sum\limits_{d|i,d|k}\mu(d)=\sum\limits_{d|k}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(id)$$
注意到$\mu(id)=[i\perp d]\ ?\ 0:\mu(i)\cdot \mu(d)$,故
$$G(n,k)=\sum\limits_{d|k}\mu^2(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)[i\perp d]=\sum\limits_{d|k}\mu^2(d)G(\lfloor\frac{n}{d}\rfloor,d)$$

$G$函数可以通过递归记忆化求出。

 1 #include<map>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=5000010,K=2010;
 9 ll ans;
10 bool b[N];
11 int tot,w,n,m,k,F[K],p[N],miu[N];
12 map<int,int>G[K],Miu;
13 
14 int gcd(int a,int b){ return b ? gcd(b,a%b) : a; }
15 int f(int n){ return (n/k)*F[k]+F[n%k]; }
16 
17 void pre(int n){
18     miu[1]=1;
19     rep(i,2,n){
20         if (!b[i]) p[++tot]=i,miu[i]=-1;
21         for (int j=1; j<=tot && i*p[j]<=n; j++){
22             b[i*p[j]]=1;
23             if (i%p[j]==0) { miu[i*p[j]]=0; break; }
24                 else miu[i*p[j]]=-miu[i];
25         }
26     }
27     rep(i,2,n) miu[i]+=miu[i-1];
28 }
29 
30 int Mu(int n){
31     int res=1;
32     if (n<=w) return miu[n];
33     if (Miu.count(n)) return Miu[n];
34     for (int i=2,lst; i<=n; i=lst+1)
35         lst=n/(n/i),res-=Mu(n/i)*(lst-i+1);
36     return Miu[n]=res;
37 }
38 
39 int g(int n,int k){
40     int res=0;
41     if (!n) return 0;
42     if (G[k].count(n)) return G[k][n];
43     if (k==1) return Mu(n);
44     for (int d=1; d*d<=k; d++)
45         if (k%d==0){
46             if (miu[d]-miu[d-1]) res+=g(n/d,d);
47             if (d*d==k) continue;
48             int t=k/d;
49             if (miu[t]-miu[t-1]) res+=g(n/t,t);
50         }
51     return G[k][n]=res;
52 }
53 
54 int main(){
55     freopen("cycle.in","r",stdin);
56     freopen("cycle.out","w",stdout);
57     scanf("%d%d%d",&n,&m,&k); w=min(max(n,m),5000000); pre(w);
58     rep(i,1,k) F[i]=F[i-1]+(gcd(i,k)==1);
59     for (int i=1,lst; i<=m && i<=n; i=lst+1)
60         lst=min(n/(n/i),m/(m/i)),ans+=1ll*(g(lst,k)-g(i-1,k))*f(m/i)*(n/i);
61     printf("%lld\n",ans);
62     return 0;
63 }

 

[NOI2016]循环之美(杜教筛)

原文:https://www.cnblogs.com/HocRiser/p/9494834.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!