C/C++教程

CF1334E Divisor Paths

本文主要是介绍CF1334E Divisor Paths,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

这是一道数论题,而不是图论题。

整个思路大概可以分成两步走:构造最短路,最短路计数。当然都是数学方法。

一、构造最短路

有一个我到最后也没猜出来的结论:\(u\) 和 \(v\) 之间的最短路,一定经过 \(\gcd(u,v)\)

要理解这句话,必须先明白题目里路径长度的含义:\(d(y)-d(x)\),\(d\)为约数个数函数。乘上一个质数 \(p\),约数个数增多;除掉 \(p\),约数个数减少。因此,如果我们不是从 \(u\) 直奔 \(\gcd(u,v)\),我们势必会因为乘上了多余的质数而走“冤枉路”。

仍然不理解?可以发现,如果不是从 \(u\) 直奔 \(\gcd(u,v)\),我们一定会做乘法,而乘上的数又会被除掉(类似上山再下山),有的边权被加了两次。否则,我们一路除掉 \(u\) 有 \(v\) 没有的质因数(一路下坡),不会出现“加两次”的状况,路程就是 \(d(u)+d(v)-2\times d(\gcd(u,v))\)。

\(v\) 到 \(\gcd(u,v)\) 的过程相似。

有一个问题:为什么不走 \(\text{lcm}(u,v)\) 呢?我不会证明,只会感性理解(走到 \(\text{lcm}(u,v)\) 增加的约数更大,可能造成更多的因子个数?)Codeforces题解下面的评论区里有人给出了详细证明

二、最短路计数

设 \(cnt\) 为 \(x\gets\dfrac{u}{\gcd(u,v)}\) 的质因子个数,\(cnt_v\) 为每个质因子各自的数目,从 \(u\) 到 \(\gcd(u,v)\) 最短路条数为 \(ans\),就有如下算式:

\( \large ans=\dfrac{cnt!}{\prod\limits_{v\in \text{prime}}^{v\vert x}cnt_v!} \)

运用组合数学知识,正确性显然。

三、AC 代码(部分)

inline LL solve(LL x){
	LL sum=0,a,b=1;
	for(int i=1;i<=tot;++i){
		LL cnt=0;
		while(x%p[i]==0) ++cnt,x/=p[i];
		b=b*fac[cnt]%MOD;
		sum+=cnt;
	}
	a=fac[sum];
	return a*_pow(b,MOD-2)%MOD;
}
int main(){
	LL D,q;
	scanf("%lld%lld",&D,&q);
	fac[0]=1;
	for(int i=1;i<=100;++i) fac[i]=fac[i-1]*i%MOD;
	LL d=D;
	for(LL i=2;i*i<=D;++i){
		if(d%i==0) p[++tot]=i;
		while(d%i==0) d/=i;
	}
	if(d>1) p[++tot]=d;
	while(q--){
		LL u,v;
		scanf("%lld%lld",&u,&v);
		LL g=gcd(u,v);
		printf("%lld\n",solve(u/g)*solve(v/g)%MOD);
	}
	return 0;
}

THE END

这篇关于CF1334E Divisor Paths的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!