T = 10000
N, M <= 10000000
ans=Σ Σ μ(T/p) floor(n/T)floor(m/T)
T p\T
此公式不会看这里
现在是枚举 T、P,肯定 TLE
所以继续推
令 f(T)=Σ μ(T/p) p 为素数
p\T
根据线性筛的思路
当 T 为素数时 只有 p=T,∴f(T)=μ(1)=1
当 T 不为素数时,
令 T=i*prime[j]
对 i 分解质因数,i=p1^k1*p2^k2*p3^k3……
当 i%prime[j]!=0 时, f[i]=Σ μ(i/p)=μ(p1^(k1-1)*p2^k*p3^k……)+μ(p1^k1*p2^(k2-1)*p3^k3……)+μ(p1^k1*p2^k2*p3^(k3-1)……)+……
p\i
为了方便表示,令 s1=μ(p1^(k1-1)*p2^k*p3^k……) s2=μ(p1^k1*p2^(k2-1)*p3^k3……) s3=μ(p1^k1*p2^k2*p3^(k3-1)……) ……
f[T]=Σ μ(T/p)=μ(s1*prime[j])+μ(s2*prime[j])+μ(s3*prime[j])+……+μ(T/prime[j])
p\T
= μ(prime[j])*(μ(s1)+μ(s2)+μ(s3)+……)+μ(T/prime[j])
=μ(prime[j])*f(i)+μ(i)
=-f(i)+μ(i)
当 i%prime[j]==0 时,i 分解质因数,其中必有一个 pi=prime[j]
∴上面 f(T)中每一项中,除最后一项外,前面每一项的 prime[j] 都可以与 si 中的 1 个 pi 合并为一个,即出现了 pi^ki ki>=2
∴f(T)除最后一项都 = 0
看最后一项,μ(T/prime[j]),因为 T=i*prime[j],所以 prime[j] 约去
所以最优后一项 =μ(i)
综上所述,线性筛时,枚举 i
当 i 为素数时 f(i)=1
当 i%prime[j]!=0 时,f(i*prime[j])= μ(i)-f(i)
当 i%prime[j] =0 时, f(i*prime[j])=μ(i)
为什么这里把 T 是素数换成了 i 是素数
因为线性筛的过程,T 若是素数,一定可以在某个 i 时被枚举到
然后 i*prime[j] 就相当于推导过程中的 T
- #include
- #include
- #define N 10000001
- using namespace std;
- int t;
- long long x,y;
- int prime[N],miu[N],cnt,f[N],sum[N];
- bool v[N];
- void pre()
- {
- miu[1]=1;
- for(int i=2;i)
- {
- if(!v[i])
- {
- v[i]=true;
- prime[++cnt]=i;
- miu[i]=-1;
- f[i]=1;
- }
- for(int j=1;j<=cnt;j++)
- {
- if(i*prime[j]>N-1) break;
- v[i*prime[j]]=true;
- if(i%prime[j]==0)
- {
- miu[i*prime[j]]=0;
- f[i*prime[j]]=miu[i];
- break;
- }
- miu[i*prime[j]]=-miu[i];
- f[i*prime[j]]=miu[i]-f[i];
- }
- }
- for(int i=1;i1]+f[i];
- }
- void solve()
- {
- long long k=min(x,y),j,ans=0;
- for(long long i=1;i<=k;i=j+1)
- {
- j=min(x/(x/i),y/(y/i));
- ans+=(x/i)*(y/i)*(sum[j]-sum[i-1]);
- }
- printf("%lld\n",ans);
- }
- int main()
- {
- pre();
- scanf("%d",&t);
- while(t--)
- {
- scanf("%lld%lld",&x,&y);
- solve();
- }
- }
元元真厉害 \(^o^)/~
我的智商啊~~~~(>_<)~~~~
来源: http://www.bubuko.com/infodetail-1995306.html