Description
Input
Output
Sample Input
Sample Output
explanation
满足条件的数分别是:
1/1=1.0000……
1/3=0.3333……
2/1=2.0000……
2/3=0.6666……
1/1 和 2/2 虽然都是纯循环小数,但因为它们相等,因此只计数一次;同样,1/3 和 2/6 也只计数一次。
判断一个分数$frac{x}{y}$是否是纯循环小数,就是一直除,直到出现了相同余数x,即
$$xk^l equiv x (mod y)$$
$$l
eq 0$$
要求值不重复,所以$x perp y$
可以推得$k^l equiv 1(mod y)$,条件也就是$y perp k$
答案就是egin{aligned}&\&sum_{y=1}^{m}[yperp k]sum_{x=1}^{n}[xperp y]end{aligned}
莫比乌斯反演得
egin{aligned}&sum_{y=1}^{m}[yperp k] sum_{x=1}^{n}sum_{d|x,d|y}mu(d)\=&sum_{y=1}^{m}[yperp k]sum_{d|y}^{n}mu(d)lfloor frac{n}{d}
floor end{aligned}
交换顺序
egin{aligned}&sum_{d=1}^{n}mu(d)lfloor frac{n}{d}
floor sum_{y=1}^{m}[d | y][yperp k]\=&sum_{d=1}^{n}mu(d)lfloor frac{n}{d}
floor sum_{i=1}^{lfloor frac{m}{d}
floor}[idperp k]\=& sum_{d=1}^{n}[dperp k]mu(d)lfloor frac{n}{d}
floor sum_{i=1}^{lfloor frac{m}{d}
floor}[iperp k]end{aligned}
令f[n]=$sum_{d=1}^{n}[iperp k]$
由同余性质:
gcd(a,b)=gcd(a%b,b)
$f(n)=left lfloor frac{n}{k}
ight
floor f(k)+f(n mod k)$
这样84分就有了O(n)计算就行
设$g(n,k)=sum_{i=1}^n[iperp k]mu(i)$
考虑将k分解成pcq (p是素数)
于是可以将只与q互质的答案减去不与p互质的答案,不与素数p互质就是p的倍数
egin{aligned} g(n,k)&=sum_{i=1}^n[iperp q]mu(i)-sum_{y=1}^{lfloorfrac{n}{p}
floor}[pyperp q]mu(py) \&=g(n,q)- sum_{y=1}^{lfloorfrac{n}{p}
floor}[yperp q]mu(py)end{aligned}
显然当$pperp y$的时候$mu(py)=mu(p)mu(y)$,否则$mu(py)=0$
还有$mu(p)=-1$
egin{aligned} g(n,k)&=g(n,q)- sum_{y=1}^{lfloorfrac{n}{p}
floor}[yperp p][yperp q]mu(p)mu(y)\&=g(n,q)-mu(p)sum_{y=1}^{lfloorfrac{n}{p}
floor}[yperp k]mu(y)\&=g(n,q)+g(lfloorfrac{n}{p}
floor,k) end{aligned}
递归求解容易发现边界情况就是$n=0$或者$k=1$。$n=0$的时候直接返回$0$就可以了,$k=1$的时候就是莫比乌斯函数的前缀和,用杜教筛求出
递归时记忆化,直接用map
由于每次递归要么$n$会变成$lfloor frac{n}{p}
floor$,有$O(sqrt{n})$种取值;要么$p$少了一个质因数,有$omega(k)$种取值,所以总共有$O(omega(k)sqrt{n})$种取值,记忆化搜索即可。其中$omega(k)$表示$k$的不同的质因子数目。于是最后的总复杂度为$O(omega(k)sqrt{n}+n^{frac{2}{3}})$
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<map> 7 using namespace std; 8 typedef long long lol; 9 lol mu[8000001],prime[4000001]; 10 lol tot,N=8000000,cnt; 11 lol d[10001],f[2001],ans; 12 bool vis[8000001]; 13 map<lol,lol>M1; 14 map<lol,map<lol,lol> >M2; 15 int gcd(int a,int b) 16 { 17 if (!b) return a; 18 return gcd(b,a%b); 19 } 20 void pre(lol k) 21 {lol i,j; 22 mu[1]=1; 23 for (i=2;i<=N;i++) 24 { 25 if (vis[i]==0) 26 { 27 prime[++tot]=i; 28 mu[i]=-1; 29 } 30 for (j=1;j<=tot;j++) 31 { 32 if (i*prime[j]>N) break; 33 vis[i*prime[j]]=1; 34 if (i%prime[j]==0) 35 { 36 mu[i*prime[j]]=0; 37 break; 38 } 39 else mu[i*prime[j]]=-mu[i]; 40 } 41 } 42 for (i=1;i<=N;i++) 43 mu[i]+=mu[i-1]; 44 lol kk=k; 45 for (i=2;i<=k;i++) 46 { 47 if (kk%i==0) d[++cnt]=i; 48 while (kk%i==0) kk/=i; 49 } 50 } 51 lol get_mu(lol n) 52 {lol i,pos; 53 if (n<=N) return mu[n]; 54 if (M1[n]) return M1[n]; 55 lol s=1; 56 for (i=2;i<=n;i=pos+1) 57 { 58 pos=n/(n/i); 59 s-=(pos-i+1)*get_mu(n/i); 60 } 61 return M1[n]=s; 62 } 63 lol get_s(lol n,lol k) 64 { 65 if (n<=1) return n; 66 if (k==0) return get_mu(n); 67 if (M2[n][k]) return M2[n][k]; 68 return M2[n][k]=get_s(n,k-1)+get_s(n/d[k],k); 69 } 70 lol get_f(lol n,lol k) 71 { 72 return (n/k)*f[k]+f[n%k]; 73 } 74 int main() 75 {lol n,m,k; 76 lol i,pos; 77 cin>>n>>m>>k; 78 for (i=1;i<=k;i++) 79 { 80 if (gcd(i,k)==1) f[i]=1; 81 f[i]+=f[i-1]; 82 } 83 N=min(N,max(n,m)); 84 pre(k); 85 for (i=1;i<=min(n,m);i=pos+1) 86 { 87 pos=min(n/(n/i),m/(m/i)); 88 ans+=(n/i)*(get_s(pos,cnt)-get_s(i-1,cnt))*get_f(m/i,k); 89 } 90 cout<<ans; 91 }