bzoj5332&loj2565 [Sdoi2018]旧试题

bzoj5332&loj2565 [Sdoi2018]旧试题

​​ 题目地址​​​ 首先知道结论 原题所求可以转化为 ∑i=1A∑j=1B∑k=1C∑x|i∑y|j∑z|k[gcd(x,y)=1][gcd(x,z)=1][gcd(y,z)=1] ∑ i = 1 A ∑ j = 1 B ∑ k = 1 C ∑ x | i ∑ y | j ∑ z | k [ g c d ( x , y ) = 1 ] [ g c d ( x , z ) = 1 ] [ g c d ( y , z ) = 1 ] ∑x=1A∑y=1B∑z=1C[gcd(x,y)=1][gcd(x,z)=1][gcd(y,z)=1]⌊Ax⌋⌊By⌋⌊Cz⌋ ∑ x = 1 A ∑ y = 1 B ∑ z = 1 C [ g c d ( x , y ) = 1 ] [ g c d ( x , z ) = 1 ] [ g c d ( y , z ) = 1 ] ⌊ A x ⌋ ⌊ B y ⌋ ⌊ C z ⌋ 针对每个gcd莫比乌斯反演 ∑x=1A∑y=1B∑z=1C∑i|x,i|yμ(i)∑j|x,j|zμ(j)∑k|y,k|zμ(k)⌊Ax⌋⌊By⌋⌊Cz⌋ ∑ x = 1 A ∑ y = 1 B ∑ z = 1 C ∑ i | x , i | y μ ( i ) ∑ j | x , j | z μ ( j ) ∑ k | y , k | z μ ( k ) ⌊ A x ⌋ ⌊ B y ⌋ ⌊ C z ⌋ ∑i=1A∑j=1B∑k=1Cμ(i)μ(j)μ(k)∑i|x,j|x⌊Ax⌋∑i|y,k|y⌊By⌋∑j|z,k|z⌊Cz⌋ ∑ i = 1 A ∑ j = 1 B ∑ k = 1 C μ ( i ) μ ( j ) μ ( k ) ∑ i | x , j | x ⌊ A x ⌋ ∑ i | y , k | y ⌊ B y ⌋ ∑ j | z , k | z ⌊ C z ⌋ 后面这个带下去整符号的东西我们可以考虑n log(n)预处理 设fn(i)=∑i|dnnd f n ( i ) = ∑ i | d n n d 那么因为后面的东西是i|x,j|x i | x , j | x 所以直接给他换成lcm的倍数即可 然后考虑这直接暴力是n^3但是显然当f函数的i>n的时候是0 所以我们考虑如何求解 首先把i,j,k都相同的枚举 算答案再算两两相同的答案 n=max(A,B,C); 设点x,y 只有当他们的lcm< n的时候把他们加入然后给无向图定向 使得点度小的往大的连如果相同编号小->大 这样保证每个点出度是sqrt(n) 然后最后再去暴力枚举三元环即可 因为顺序问题 分六种情况讨论 前面的枚举两两相同的采取枚举lcm的方式可以使得复杂度是n∗log(n)2 n ∗ l o g ( n ) 2

#include#include#include#include#include#define fi first#define se second#define ll long long#define pa pair#define mp(x,y) make_pair(x,y)using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;const int mod=1e9+7;inline int gcd(int x,int y){return !y?x:gcd(y,x%y);}ll ans,fa[N],fb[N],fc[N];bool not_prime[N];vector eg[N];int T,prime[N],tot,mu[N],A,B,C,n,sa[N],sb[N],sc[N],d[N];inline void init(){ mu[1]=1; for (int i=2;i<=1e5;++i){ if (!not_prime[i]) prime[++tot]=i,mu[i]=-1; for (int j=1;prime[j]*i<=1e5;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0){ mu[prime[j]*i]=0;break; }else mu[prime[j]*i]=-mu[i]; } }}struct node{ int x,y,z;}data[N*10];inline void insert1(int x,int y,int z){eg[x].push_back(mp(y,z));}inline bool check(int i){ int x=data[i].x,y=data[i].y; return d[x]==d[y]?xk) continue;data[++tot]=(node){x,y,z};++d[x];++d[y]; } } } for (int i=1;i<=tot;++i) if (check(i)) insert1(data[i].x,data[i].y,data[i].z); else insert1(data[i].y,data[i].x,data[i].z); for (int i=1;i<=n;++i){ for (int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。