Codeforces Global Round 17 D. Not Quite Lee（gcd）

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
ll qpow(ll a, ll b)
{
  ll res = 1;
  while(b)
  {
    if(b&1)res = res*a%mod;
    b = b>>1;
    a = a*a%mod;
  }
  return res;
}
int sum[40];
ll a[200010];
ll suf[40]; 
int main()
{
  int n;
  cin>>n;
  ll even = 0,odd = 0;
  for(int i = 1; i <= n; i++)
  {
    cin>>a[i];
    if(a[i]%2)odd++;
    else even++;
    if(a[i]%2==0)
    {
      int k = 0;
      ll now = a[i];
      while(now%2==0)
      {
        now/=2;
        k++;
      }
      sum[k]++;
    }
  }
  for(int i = 31; i >= 1; i--)
  {
    suf[i] = suf[i+1]+sum[i];
  }
  ll ans = qpow(2,n)+mod-qpow(2,even);
  ans%=mod;
  for(int i = 1; i <= 31; i++)
  {
    if(sum[i])
    {
      ans += (qpow(2,sum[i]-1)-1)*qpow(2,suf[i+1]);
      ans%=mod;
    }
  }
  cout<<ans%mod<<endl;
}