牛客竞赛题目讲解_孤独的树

// https://ac.nowcoder.com/acm/contest/11225/F

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <algorithm>

#include <iostream>

#include <cstring>

 #include <vector>

using namespace std;

int n,i,j;

 

int a[100005]={0,32,2,2,2,2};

int edge[32][2]={

1, 2,

1, 3,

1, 4,

1,5

};

vector<int> v[100005];

int ans;

 int gcd(int a,int b)

{    

    if(a%b==0) 

    return b;        

    else return (gcd(b,a%b));

}

int pcount(int t)

{

if(t==1)return 0;

int pc=0; 

  for(int i=2;t>1;i++)               

                while(t%i==0)t/=i,pc++;         

  return pc;

}

void dfs(int x,int fa){

    for(int y:v[x])if(y!=fa){

        dfs(y,x);

        int t=gcd(a[x],a[y]);

        ans+=pcount(t);

        a[x]/=t;

cout<<" a[x]="<<a[x]<<"  t="<<t<<endl;

    }

}

int main()

{

n=5;

    //cin>>n;

   // for(int i=1;i<=n;i++)cin>>a[i]; 

    for(int i=1;i<n;i++){

        int x,y;

x=edge[i-1][0];

y=edge[i-1][1];

        //cin>>x>>y;

        v[x].push_back(y);

        v[y].push_back(x);

    }

     dfs(1,0);

    cout<<ans<<endl;

    return 0;

}