Codeforces 990G. GCD Counting

80 阅读 0 评论 53 点赞

我是靠谱客的博主眼睛大白羊，最近开发中收集的这篇文章主要介绍Codeforces 990G. GCD Counting，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目连接：http://codeforces.com/contest/990/problem/G

题目描述：

You are given a tree consisting of $n n$ vertices. A number is written on each vertex; the number on vertex $i i$ is equal to $a_{i} ai$ .

Let's denote the function $g (x, y) g(x,y)$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $x x$ to vertex $y y$ (including these two vertices).

For every integer from $11$ to $2 \cdot 10^{5} 2\cdot105$ you have to count the number of pairs $(x, y) (x,y)$ $(1 \leq x \leq y \leq n) (1\leqx\leqy\leqn)$ such that $g (x, y) g(x,y)$ is equal to this number.

Input

The first line contains one integer $n n$ — the number of vertices $(1 \leq n \leq 2 \cdot 10^{5}) (1\leqn\leq2\cdot105)$ .

The second line contains $n n$ integers $a_{1} a1$ , $a_{2} a2$ , ..., $a_{n} an$ $(1 \leq a_{i} \leq 2 \cdot 10^{5}) (1\leqai\leq2\cdot105)$ — the numbers written on vertices.

Then $n - 1 n-1$ lines follow, each containing two integers $x x$ and $y y$ $(1 \leq x, y \leq n, x \neq y) (1\leqx,y\leqn,x\neqy)$ denoting an edge connecting vertex $x x$ with vertex $y y$ . It is guaranteed that these edges form a tree.

Output

For every integer $i i$ from $11$ to $2 \cdot 10^{5} 2\cdot105$ do the following: if there is no pair $(x, y) (x,y)$ such that $x \leq y x\leqy$ and $g (x, y) = i g(x,y)=i$ , don't output anything. Otherwise output two integers: $i i$ and the number of aforementioned pairs. You have to consider the values of $i i$ in ascending order.

See the examples for better understanding.

Examples

input

Copy
3
1 2 3
1 2
2 3

output

Copy
1 4
2 1
3 1

input

Copy
6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5

output

Copy
1 6
2 5
4 6
8 1
16 2
32 1

input

Copy
4
9 16 144 6
1 3
2 3
4 3

output

Copy
1 1
2 1
3 1
6 2
9 2
16 2
144 1

题解：由于2e5内gcd不会有太多种，所以直接暴力回溯。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int val[maxn];
ll cnt[maxn];
vector<int>g[maxn];
map<int, ll> c[maxn];
void dfs(int u, int p = 0)
{
c[u][val[u]] ++;
for(int v : g[u]) {
if(v != p) {
dfs(v, u);
for(auto itu : c[u]) {
for(auto itv : c[v]) {
cnt[__gcd(itu.first, itv.first)] += itu.second * itv.second; //先统计个数
}
}
for(auto itv : c[v]) {
c[u][__gcd(val[u], itv.first)] += itv.second; //在进行更新.
}
c[v].clear(); //must clear, or it will be MLE
}
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
for(int i = 1;i <= n;i ++) {
cin >> val[i];
cnt[val[i]] ++;
}
for(int i = 1;i < n;i ++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1);
for(int i = 1;i < maxn;i ++) {
if(cnt[i]) cout << i << ' ' << cnt[i] << 'n';
}
return 0;
}