GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday, 4 September 2022

[Solution] Electrical Efficiency Codeforces Solution


E. Electrical Efficiency
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the country of Dengkleknesia, there are N factories numbered from 1 to N. Factory i has an electrical coefficient of Ai. There are also N1 power lines with the j-th power line connecting factory Uj and factory Vj. It can be guaranteed that each factory in Dengkleknesia is connected to all other factories in Dengkleknesia through one or more power lines. In other words, the collection of factories forms a tree. Each pair of different factories in Dengkleknesia can use one or more existing power lines to transfer electricity to each other. However, each power line needs to be turned on first so that electricity can pass through it.

Define f(x,y,z) as the minimum number of power lines that need to be turned on so that factory x can make electrical transfers to factory y and factory z. Also define g(x,y,z) as the number of distinct prime factors of GCD(Ax,Ay,Az).

To measure the electrical efficiency, you must find the sum of f(x,y,z)×g(x,y,z) for all combinations of (x,y,z) such that 1x<y<zN. Because the answer can be very large, you just need to output the answer modulo 998244353.

Note: GCD(k1,k2,k3) is the greatest common divisor of k1k2, and k3, which is the biggest integer that simultaneously divides k1k2, and k3.

Input

The first line contains a single integer N (1N2105) — the number of factories in Dengkleknesia.

Solution Click Below:-  ðŸ‘‰CLICK HERE👈
👇👇👇👇👇

The second line contains N integers A1,A2,,AN (1Ai2105) — the electrical coefficients of the factories.

The j-th of the next N1 lines contains two integers Uj and Vj (1Uj,VjN) — a power line that connects cities Uj and Vj. The collection of factories forms a tree.

Output

An integer representing the sum of f(x,y,z)×g(x,y,z) for all combinations of (x,y,z) such that 1x<y<zN, modulo 998244353


Note

In the first example, the only (x,y,z) possible is (1,2,3). Because GCD(A1,A2,A3)=GCD(1,2,3)=1 has 0 distinct prime factors, therefore f(x,y,z)×g(x,y,z)=2×0=0.

In the second example, all triples (x,y,z) that satisfy the condition are as follows:

  • (1,2,3)f(1,2,3)×g(1,2,3)=2×1=2
  • (1,2,4)f(1,2,4)×g(1,2,4)=2×1=2
  • (1,3,4)f(1,3,4)×g(1,3,4)=3×2=6
  • (2,3,4)f(2,3,4)×g(2,3,4)=2×1=2

So the electrical efficiency is 2+2+6+2=12.

No comments:

Post a Comment