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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。