B. Kamil and Making a Stream


Codeforces Round #588 (Div. 1) B. Kamil and Making a Stream

题目：

要求求出所有的f(u , v)之和， u是v的祖先节点， f(u , v)是__gcd(u , .... u1 , u2 ... v),__其中u1 , u2 ...... 是u到v路径的所有节点。

inputCopy
5
4 5 6 0 8
1 2
1 3
1 4
4 5
outputCopy
42

优雅的暴力：

性质：可以发现u->v路径上的点越多，gcd越小，也就是有单调性。

那么我们用vector存一下u到根节点的所有f()值，肯定是单调的。

这个地方可以用个小技巧，gcd个数不会很多，log级别的个数(具体为啥，可以查看一下gcd性质) , 所以会有很多重复的，就用vector> , 存一个gcd是多少， 这个gcd有多少个。

然后就暴力的从父亲节点身上，搞到了当前节点身上。

好优雅的暴力。

/*
 *@author spnooyseed
 */
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int n ;
vector v[N] ;
vector > ans[N] ;
ll a[N] ;
void dfs(int u , int f) {
  if(f) {

    for(auto x : ans[f]) {
      ll d = __gcd(a[u] , x.x) ;
      if(ans[u].empty() || ans[u].back().x != d) ans[u].push_back({d , x.y}) ;
      else ans[u].back().y += x.y ;
    }

  }
  if(ans[u].empty() || ans[u].back().x != a[u]) ans[u].push_back({a[u] , 1}) ;
  else ans[u].back().y ++ ;
  for(auto x : v[u]) {
    if(x != f)
     dfs(x , u) ;
  }
  return  ;
}
int work()
{
  scanf("%d" , &n) ;
  for(int i = 1; i <= n ;i ++ ) scanf("%lld" , &a[i]) ;
  for(int i = 1; i < n ;i ++ ) {
    int a , b ;
    scanf("%d%d" , &a , &b) ;
    v[a].push_back(b) , v[b].push_back(a) ;
  }
  dfs(1 , 0) ;
  ll cnt = 0 ;
  for(int i = 1; i <= n ;i ++ )
   for(auto x : ans[i])
     cnt += x.x * x.y % mod , cnt %= mod ;
  cout << cnt % mod << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
*/
优雅的暴力CodeForces

相关

Codeforces Round 628 (Div. 2) E. Ehab's REAL Number Theory Problem

Codeforces Round #610 (Div. 2)

Codeforces Global Round 6.E题

Codeforces Round #611 (Div. 3) E题

CF1545X Codeforces Round #732

codeforces和atcoder的思维题目

Codeforces 1373F - Network Coverage（模拟网络流）

CF1481X Codeforces Round #699

CF1485X Codeforces Round #701

Educational Codeforces Round 7 F. The Sum of the k-th Powers 拉格朗日插值法

Codeforces #731 (div3) E. Air Conditioners

Codeforces Round #675

标签