数学，结论题

告诉大家一个结论。
求解任意区间的gcd中，gcd的变化最多只有log2(max(num))次

为什么这样说呢？
现在假设我们求解从L到后面任意一个前缀的gcd
我们想想哈，这个gcd值一定是<=a[L]的
我们想想这个gcd的变化，每次变化最小还是得/2那么最多log2(a[L])次
实际上变化的还会更少！！！

那么依据这个理论，我们可以做出这题。
时空复杂度其实是很小的。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int max_n = 1e5+100;
const ll mod = 1e9+7;
struct edge{
    int to,next;
}E[max_n<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;
    E[cnt].next=head[from];
    head[from]=cnt++;
}
ll x[max_n];
int n;
map<ll,ll> mp[max_n];
ll ans=0;
void dfs(int u,int fa){
    mp[u][x[u]]++;
    for (pll it:mp[fa])mp[u][__gcd(it.first,x[u])]+=it.second;
    for (int i=head[u];i;i=E[i].next)
        if (E[i].to!=fa)dfs(E[i].to,u);
    for (pll it:mp[u])ans = (ans+it.first*it.second)%mod;
}
int main(){
    cin>>n;
    for (int i=1;i<=n;++i)cin>>x[i];
    for (int i=1,u,v;i<n;++i){
        cin>>u>>v;
        add(u,v);add(v,u);
    }dfs(1,0);
    cout<<ans<<endl;
}