51 nod 1222 最小公倍数计数

Description

定义F(n)表示最小公倍数为n的二元组的数量。 即：如果存在两个数（二元组）X，Y(X <= Y)，它们的最小公倍数为N，则F(n)的计数加1。 例如：F(6) = 5，因为[2,3] [1,6] [2,6] [3,6] [6,6]的最小公倍数等于6。

给出一个区间[a,b]，求最小公倍数在这个区间的不同二元组的数量。 例如：a = 4，b = 6。符合条件的二元组包括： [1,4] [2,4] [4,4] [1,5] [5,5] [2,3] [1,6] [2,6] [3,6] [6,6]，共10组不同的组合。

Input

输入数据包括2个数：a, b，中间用空格分隔（1 <= a <= b <= 10^11)。

Output

输出最小公倍数在这个区间的不同二元组的数量。

Input示例

4 6

Output示例

10

Solution

忽略x<=y这个条件

ans=∑i=1n∑j=1n[ijgcd(i,j)<=n] 双sigma+gcd？直接考虑反演 为方便考虑，下取整忽略不写，即除法默认下取整 套路得 ans=∑d=1n∑i=1n∑j=1n[gcd(i,j)=1][ijd<=n] 设f[d]表示gcd(i,j)=d满足上面的条件的个数 f[d]=∑i=1nd∑j=1nd[ijd2<=n] 代回 ans=∑k=1n∑d=1nμ(d)∑i=1nd∑j=1nd[kijd2<=n] ans=∑d=1nμ(d)∑k=1n∑i=1nd∑j=1nd[kij<=nd2] 即求 k∗i∗j<n 先假设 k<i<j 那么结果*6 再假设 k=i<j和k<i=j 结果*3 最后再加上X<=Y这个限制即ans=(ans+n)/2

Code

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define N 501000 #define fo(i,a,b) for(ll i=a;i<=b;i++) #define ll long long using namespace std; ll mu[N],p[N],bz[N],s[N]; ll calc(ll n) { ll ans=0; for(ll d=1;(ll)d*d<=n;d++) if(mu[d]!=0) { ll t=(n/d/d),an=0; for(ll a=1;(ll)a*a*a<=t;a++) { for(ll b=a+1;(ll)a*b*b<=t;b++) an+=((t/a/b)-b)*6+3; an++; an+=((t/a/a)-a)*3; } ans+=an*mu[d]; } return (ans+n)/2; } int main() { mu[1]=1; fo(i,2,N-1) { if (bz[i]==0) p[++p[0]]=i,mu[i]=-1; fo(j,1,p[0]) { int x=i*p[j]; if(x>N-1) break; bz[x]=1; if(i%p[j]==0) {mu[x]=0;break;} mu[x]=-mu[i]; } } ll n,m; scanf("%lld %lld",&n,&m); ll ans=calc(m); ans-=calc(n-1); printf("%lld",ans); }