【点分治练习】[hdu4812]multik

2015年1月12日2,2716

【问题描述】

给定一棵 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)

 

  • 郭天成2015年6月3日 下午10:01 回复

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

    #1  
    • hzwer2015年6月3日 下午10:44 回复
      admin

      freopen没去掉貌似

      #11
  • 夜末蓅-灵魂2016年7月29日 下午11:11 回复

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

    #2  
    • fuboat2016年7月30日 上午10:13 回复

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

      #21
  • fuboat2016年7月30日 上午10:20 回复

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

    #3  
    • %fuboat2016年7月30日 下午1:52 回复

      %%fuboat

      #31