懵逼钨丝繁衍,你值得拥有
若我们需要一个函数 f(x) f ( x ) ,它非常的不好求 同时我们有一个函数 F(x) F ( x ) ,它非常的好求 并且 f(x) f ( x ) 与 F(x) F ( x ) 之间的关系为:
F(n)=∑d|nf(d) F ( n ) = ∑ d | n f ( d ) 或者 F(n)=∑n|df(d) F ( n ) = ∑ n | d f ( d ) 那么我们就可以得到 f(x) f ( x ) 的计算式 f(x)=∑d|nμ(n/d)f(d) f ( x ) = ∑ d | n μ ( n / d ) f ( d ) 或者是 f(x)=∑n|dμ(d/n)f(d) f ( x ) = ∑ n | d μ ( d / n ) f ( d ) 其中 μ(x) μ ( x ) 是莫比乌斯函数 定义为 ⎧⎩⎨μ(1)=1μ(x)=(−1)kμ(x)=0x=p1∗p2∗⋯∗pk,p1>p2>⋯>pk,p∈primeotherwise { μ ( 1 ) = 1 μ ( x ) = ( − 1 ) k x = p 1 ∗ p 2 ∗ ⋯ ∗ p k , p 1 > p 2 > ⋯ > p k , p ∈ p r i m e μ ( x ) = 0 o t h e r w i s e μ μ 可以在线性时间内处理出来(利用素数筛)其实本质上这就是一个很巧妙的容斥
首先可以把不好求的 f(x) f ( x ) 求出来 其次还是可以把不好求的 f(x) f ( x ) 求出来 其实就是将求 f(x) f ( x ) 的巨大时间复杂度转化为求 F(x) F ( x )
非常的舒服
当 x<=a,y<=b x <= a , y <= b ,有多少组 (x,y) ( x , y ) 满足 gcd(x,y)=d g c d ( x , y ) = d
用 f(n f ( n 表示在 [1,a],[1,b] [ 1 , a ] , [ 1 , b ] 中 gcd(x,y) g c d ( x , y ) 等于 n n 的个数 用F(n)F(n)表示在 [1,a],[1,b] [ 1 , a ] , [ 1 , b ] 中 gcd(x,y) g c d ( x , y ) 是 n n 的倍数的个数
显然我们会得到 F(n)=∑n|dmin(a,b)f(d)F(n)=∑n|dmin(a,b)f(d) 这满足莫比乌斯函数的要求 于是反演一下 得到 f(n) f ( n ) 表达式
f(n)=∑n|dmin(a,b)μ(d/n)∗F(d) f ( n ) = ∑ n | d m i n ( a , b ) μ ( d / n ) ∗ F ( d )我们需要的是 gcd(x,y)=d g c d ( x , y ) = d 那么转化为求 f(d) f ( d ) 显然求 f(d) f ( d ) 的时间复杂度为 O(min(a,b)/d) O ( m i n ( a , b ) / d ) 鉴于询问有50000组,所以最坏情况时间复杂度为 O(50000∗50000) O ( 50000 ∗ 50000 ) 挂掉
所以需要优化 转化一下原来的式子 当 x<=a,y<=b x <= a , y <= b ,有多少组 (x,y) ( x , y ) 满足 gcd(x,y)=d g c d ( x , y ) = d 等价于 当 x<=a/d,y<=b/d x <= a / d , y <= b / d ,有多少组 (x,y) ( x , y ) 满足 gcd(x,y)=1 g c d ( x , y ) = 1 这样相当于
a′=⌊ad⌋,b′=⌊bd⌋ a ′ = ⌊ a d ⌋ , b ′ = ⌊ b d ⌋ F(n)=∑n|xmin(a′,b′)f(x) F ( n ) = ∑ n | x m i n ( a ′ , b ′ ) f ( x ) 求 f(1) f ( 1 ) f(1)=∑xmin(a′,b′)μ(x)∗F(x) f ( 1 ) = ∑ x m i n ( a ′ , b ′ ) μ ( x ) ∗ F ( x )式子非常的优美,其中
F(x)=⌊a′x⌋∗⌊b′x⌋ F ( x ) = ⌊ a ′ x ⌋ ∗ ⌊ b ′ x ⌋ 显然的,在求和过程中 F(x) F ( x ) 是单调不增的,并且 ⌊a′x⌋∗⌊b′x⌋ ⌊ a ′ x ⌋ ∗ ⌊ b ′ x ⌋ 最多都只有 a′−−√+b′−−√ a ′ + b ′ 种取值,那么分块求和即可Code:
#include <bits/stdc++.h> using namespace std; const int N = 50010; int t,a,b,d; int mu[N],pri[N],sum[N],tot; bool mark[N]; void get() { mu[1]=1; for(int i=2;i<=50000;++i) { if(!mark[i]) { pri[++tot]=i; mu[i]=-1; } for(int j=1;j<=tot && pri[j]*i<=50000;++j) { mark[i*pri[j]]=1; if(i%pri[j]==0) break; mu[i*pri[j]]=-mu[i]; } } for(int i=1;i<=50000;++i) sum[i]=sum[i-1]+mu[i]; } void work() { scanf("%d%d%d",&a,&b,&d); a/=d;b/=d; if(a>b) swap(a,b); int pos=0,ans=0; for(int i=1;i<=a;i=pos+1) { pos=min((a/(a/i)),(b/(b/i))); ans+=(sum[pos]-sum[i-1])*(a/i)*(b/i); } printf("%d\n",ans); } int main() { get(); scanf("%d",&t); while(t--) work(); return 0; }其他好(水)题还有: BZOJ 3930 选数 BZOJ 2154 Crash的数字表格 BZOJ 2301 Problem b BZOJ 2820 YY的Gcd BZOJ 2693 jzptab
加油吧,骚年
