Problem Description

Given a positive integers n , Mobius function μ(n) is defined as follows:

 are different prime numbers.

Given two integers mm, nn, please calculate 

Input

One line includes two integers m(1≤m≤2e9), n(1≤n≤1e12) .

Output

One line includes the answer .

Sample Input

2 2

​​​​​​​Sample ​​​​​​​Output

-1

题意：已知莫比乌斯函数，求 

思路：杜教筛

首先考虑 n 是否含平方因子，若 n 含有平方因子，那么根据莫比乌斯函数，每一项的 u(in) 均为 0，结果直接为 0

再考虑 n 不含平方因子，此时，每一个 n 都可以拆成 

设 为答案

考虑 n 的一个素因子 d，由于此时的 n 不含平方因子，那么 n/d 与 d 一定是互质的，那么有： 

由于莫比乌斯函数 u(n) 是一个积性函数，且 n/d 与 d 是互质的，那么只需要考虑 d 和 i 关系，对于 [1,m] 中的数 i 和 d 只有两种可能：互质、不互质

若 i 与 d 互质，则有：，由于 d 是素数，因此 u(d)=-1，故 

可以发现，这个式子与原式相比，多减去了一个 i 与 d 不互质的部分，因此还要加回去

考虑 [1,m] 中与 d 不互质的数，即为 [1,m] 中 d 的倍数，因此，只需要从 1 枚举到 m/d 即可，即有：

因此，最终答案即为 

即：

由于 m 十分大，因此要利用杜教筛来求前缀和，然后进行递归求值即可

值得注意的是，这类积性函数 f(x) 的 n 倍的求和都有类似的式子：

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 10000000+5; const int dx[] = {1,-1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;bool bprime[N]; LL mu[N],sum[N]; LL cnt,prime[1000000];void getMu(LL n){//线性筛求莫比乌斯函数cnt=0;mu[1]=1;//根据定义，μ(1)=1memset(bprime,false,sizeof(bprime));for(LL i=2;i<=n;i++){//求2~n的莫比乌斯函数if(!bprime[i]){prime[++cnt]=i;//存储质数mu[i]=-1;//i为质数时，μ(1)=-1}for(LL j=1;j<=cnt&&i*prime[j]<=n;j++){//枚举i之前的素数个数bprime[i*prime[j]]=true;//不是质数if(i%prime[j])//i不是prime[j]的整数倍时，i*prime[j]就不会包含相同质因子mu[i*prime[j]]=-mu[i];//mu[k]=mu[i]*mu[prime[j]]，因为prime[j]是质数，mu值为-1else{mu[i*prime[j]]=0;break;//留到后面再筛}}}for(LL i=1;i<=n;i++)sum[i]=sum[i-1]+mu[i]; } #include<tr1/unordered_map> tr1::unordered_map<LL,LL> w; LL djSumMu(LL x) {if(x<=10000000)return sum[x];if(w.find(x)!=w.end())return w[x];LL ans=1;for(LL l=2,r; l>=0&&l<=x; l=r+1) {r=x/(x/l);ans-=(r-l+1)*djSumMu(x/l);}return w[x]=ans; } bool judge(LL n){for(LL i=1;prime[i]*prime[i]<=n;i++){if(n%prime[i])continue;n/=prime[i];if(n%prime[i]==0)return true;}return false; } LL F(LL n,LL m) {if(n==1)return djSumMu(m);if(m==0)return 0;if(judge(n))return 0;LL temp=n;for(LL i=1; prime[i]*prime[i]<=n; i++) {if(n%prime[i]==0) {temp=prime[i];break;}}return F(n,m/temp)-F(n/temp,m); } int main() {getMu(10000000);LL n,m;scanf("%lld%lld",&m,&n);if(judge(n))printf("0\n");else{LL res=F(n,m);printf("%lld\n",res);}return 0; }

 

总结

以上是生活随笔为你收集整理的Easy Math（2018 ACM-ICPC 徐州赛区网络赛 D）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。