E CF R 85 div2 1334E. Divisor Paths

LINK：Divisor Paths

考试的时候已经想到结论了可是质因数分解想法错了导致自闭。

一张图一共有D个节点每个节点x会向y连边当且仅当y|x,x/y是一个质数。

设f(d)表示d的约数个数那么x->y的无向边的边权为f(x)-f(y);

每次询问两个点x,y之间的最短路径的条数有多少条,保证x|D,y|D.

不妨假设x>y.当y|x时容易发现y只需要每次在保证次数大于x的质因子上不断将自己本身的一个质数因子去掉即可。

不难发现此时最短路长度为1 因为不管中间去的方式如何最后得到的是同一个值。

可以发现此时我们完全可以把 y当成1 把x当成x/y 来计算。

可以发现x不会增加一个质因子因为最后还是要减掉这是不优的。

方案容易看出是排列数/每个质因子的阶乘。

考虑当y不整除x的时候

有几种选择 x->gcd(x,y)->y x->lcm(x,y)->y.

考虑第一种 x不可能往比gcd更小的点走因为那样走只是在白白的增加恭喜罢了同理第二种 x不会往比lcm更大的走。

可以发现 gcd(x,y)->y和x->lcm(x,y)中显然前者一定小于后者。

考虑 x->gcd(x,y) 和 lcm(x,y)->y 中也很显然前者一定小于后者。

再考虑路径x->gcd(x,y)这个东西可以证明中途的时候去跑到y的质因子上面带来的结果会更差。

综上算出两条路径的方案之积即可。

考试的时候 sb的地方是发现给出的x y质因数分解复杂度会高达1e7发现做不了。

但是我们考虑直接拿质数来筛因为都是D的因数所以拿D里面的质因数筛即可。

可以发现D里面的质因数不超过13个。

这样只用暴力分解D即可、

const ll MAXN=60;

ll D,n,top,maxx;

ll c[MAXN],w[MAXN],s[MAXN];

ll fac[MAXN],inv[MAXN];

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll ksm(ll b,ll p){ll cnt=1;while(p){if(p&1)cnt=cnt*b%mod;p=p>>1;b=b*b%mod;}return cnt;}

inline void prepare()

{

	fac[0]=1;

	rep(1,maxx,i)fac[i]=fac[i-1]*i%mod;

	inv[maxx]=ksm(fac[maxx],mod-2);

	fep(maxx-1,0,i)inv[i]=inv[i+1]*(i+1)%mod;

}

inline ll solve(ll x)

{

	ll cnt=0;

	rep(1,top,i)

	{

		c[i]=0;

		if(x%s[i]==0)while(x%s[i]==0)++c[i],x/=s[i];

		cnt+=c[i];

	}

	ll ans=fac[cnt];

	rep(1,top,i)ans=ans*inv[c[i]]%mod;

	return ans;

}

signed main()

{

	freopen("1.in","r",stdin);

	get(D);ll cc=D;

	for(ll i=2;i*i<=cc;++i)

	{

		if(cc%i==0)

		{

			s[++top]=i;

			while(cc%i==0)cc/=i,++w[top];

		}

	}

	if(cc>1)s[++top]=cc,++w[top];

	rep(1,top,i)maxx+=w[i];

	get(n);prepare();

	rep(1,n,i)

	{

		ll x,y;

		get(x);get(y);

		ll gg=gcd(x,y);

		putl(solve(x/gg)*solve(y/gg)%mod);

	}

	return 0;

}

巴特西

E CF R 85 div2 1334E. Divisor Paths

最新文章

热门文章