「点分治练习」[hdu4812] multik

2015年1月12日3,7146

「问题描述」

给定一棵 n 个点的树,每个点有权值 Vi

问是否存在一条路径使得路径上所有点的权值乘积 mod(10^6 + 3) 为 K

输出路径的首尾标号,若有多解,输出字典序最小的解

「输入格式」

第一行两个数 n,K
第二行 n 个数,表示 vi
接下来 n-1 行每行两个数 x,y 表示一条边

「输出格式」

输出两个数 a,b(a<b),无解输出”No solution”(不含引号)。

「样例输入」

5 60

2 5 2 3 3

1 2
1 3
2 4
2 5

「样例输出」

3 4

「数据规模与约定」

对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2,1≤vi ≤10^6+2

「题解」

预处理逆元

点分治查询的时候用个map就行了

复杂度O(nlogn^2)

 

说点什么

提醒
avatar
fuboat

目测学长的代码只有一个log
我用map结果T掉了QAQ

%fuboat
%fuboat

%%fuboat

夜末蓅-灵魂

请问下,逆元我这里不理解为什么可以这样子用啊

fuboat

对于两条路径的权值积x,y,满足要求的条件为xy=k(mod p)(p=10^6+3)
如果已知一条到根的路径的权值积为x,那么就要确定是否存在权值积y=k*x^(-1)(mod p)
x^(-1)(mod p)即为x的逆元
好象就是这么用?我也不清楚…

郭天成

学长您这题第一次tle最后是怎么解决的?是常数问题吗?