51nod1223 分數等式的數量

Time Limit：6 秒 Memory Limit：128GB

Description

有這樣一個分數等式： 1X+1Y=1N ，(X,Y,N > 0)。給出L，求有多少滿足X < Y <= L的等式。

例如：L = 12，滿足條件的等式有3個，分别是： 13+16=12,14+112=13,16+112=14 。

Input

輸入1個數L(1 <= L <= 10^11)

Output

輸出符合條件的等式的數量。

Sample Input

12

Sample Output

3

解題思路

∵1x+1y=x+yxy∴如果1x+1y=1n，那麼x+y|xy

令 d=gcd(x,y),x=dx′,y=dy′ ，則 dx′+dy′|x′y′d2→x′+y′|x′y′d

∵gcd(x′,y′)=1∴x′+y′|d

是以

Ans=∑X=1L∑Y=X+1L[X+Y|XY]=∑x′=1L∑y′=x′+1L[gcd(x′,y′)=1]∑x′+y′|d,y′d<=L1=∑x′=1L∑y′=x′+1L⌊Ly′x′+y′⌋[gcd(x′,y′)=1]=∑x=1L∑y=x+1L⌊Lyx+y⌋∑k|gcd(x,y)μ(k)=∑k=1Lμ(k)∑y=1Lk∑x=1y−1⌊Lkykx+ky⌋=∑k=1L√μ(k)∑y=1L√k∑T=y+12Y−1⌊Lk2yT⌋(用T代替x+y，k2>L則⌊Lk2yT⌋=0，(x+y)y>y2>Lk2−−−√同樣值為0)

最後一個下取整求和分塊處理好了。

時間複雜度？

O(∑k=1L√∑y=1L√kLk2y−−−−√)=O(∑k=1L√1k∑y=1L√kLy−−√)=O(∑k=1L√1k∑x=1L√k√L−−√x((x+1)2−x2))=O(∑k=1L√1k∑x=1L√k√L−−√)=O(∑k=1L√(L−−√k)32)<O(∑k=1L√L34k)=O(L34logL−−√)

交上去很小很小就是了。

#include<cstring>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 1001001

using namespace std;

typedef long long ll;

ll L,mu[N],pr[N];
bool bz[N];

ll sum(ll n,ll h,ll t){
    ll ans=;
    for(ll i=h,j;i<=n && i<=t;i=j+){
        j=min(t,n/(n/i));ans=ans+(n/i)*(j-i+);
    }return ans;
}

int main(){
    scanf("%lld",&L);
    mu[]=;
    for(ll i=;i<N;i++){
        if(!bz[i])mu[pr[++pr[]]=i]=-;
        for(int j=;j<=pr[] && i*pr[j]<N;j++){
            bz[i*pr[j]]=;mu[i*pr[j]]=-mu[i];
            if(i%pr[j]==){mu[i*pr[j]]=;break;}
        }
    }
    ll ans=;
    for(ll k=;k*k<=L;k++)if(mu[k])
        for(ll Y=;Y*Y*k*k<=L;Y++)ans=ans+mu[k]*sum(L/Y/k/k,Y+,Y+Y-);
    printf("%lld",ans);
}