Bài F - Codeforces Round #428 (Div.2)

Bài F:
Đề bài: Ở phía Bắc, trời đã chuyển sang màu đông và những thổ phỉ trắng đang đến gần. John Snow có một toán lính gồm n người. Trong khi cả thế giới đang chống chọi với thần Sấm thì anh ấy đang ráo riết chuẩn bị để tấn công những thổ phỉ trắng hung ác, tàn bạo này.
  Anh ấy đã tạo ra một phương pháp hết sức độc đáo để đánh giá toán lính của anh ấy mạnh đến mức nào. Gọi sức mạnh của người lính thứ i là a(i). Cứ k người người lính  i(1),i(2),...,i(k) được anh ấy gọi là clan tinh nhuệ nếu i(1)<i(2)<...<i(k) và gcd(a(i(1)),a(i(2)),...,a(i(k)))>1. Và sức mạnh của đội quân tinh nhuệ này là k.gcd(a(i(1)),a(i(2)),...,a(i(k))). Sau đó anh ấy định nghĩa rằng: Sức mạnh toán lính của anh ta chính bằng tổng sức mạnh của các đội quân tinh nhuệ.
  Nhiệm vụ của bạn là tìm sức mạnh của quân đội anh ta. Vì số có thể rất lớn, nên bạn phải in ra kết quả lấy dư với 10^9+7.
Đầu vào:
+ Dòng đầu tiên chứa số n (1<=n<=200000) - số lượng binh lính.
+ Dòng thứ hai chứa n số nguyên a(1),a(2),...,a(n)(1<=a(i)<=1000000)- kí hiệu là sức mạnh của các binh lính.
Đầu ra:
In ra một số - chính là sức mạnh của quân đội anh ta (sau khi lấy dư với 10^9+7).
Ví dụ:
Đầu vào:
3
3 3 1
Đầu ra:
12
/**/
Đầu vào:
4
2 3 4 6
Đầu ra:
39.
Chú thích:
Ở ví dụ đầu tiên, các clan là {1},{2},{1,2}, vì vậy câu trả lời là 1.3+1.3+2.3=12.
Hướng dẫn:
+ Gọi cnt(i) là số các chỉ số j thỏa mãn a(j) chia hết cho i.
Thế thì cnt(i) chính là số binh lính mà có sức mạnh là i,2i,3i,..
+ Tiếp theo, gọi ans(i) là số người trong clan với gcd=i. Để tính ans(i), chúng ta cần phải hiểu, làm thế nào để đếm số người trong một clan, mà mỗi số là bội của i. Nếu cnt(i)=c, thì nó là:
$1.\binom{c}{1}+2.\binom{c}{2}+...+c.\binom{c}{c}=\frac{1.c!}{(c-1)!.1!}+\frac{2.c!}{(c-2)!.2!}+...+\frac{c.c!}{0!.c!}=\frac{c!}{(c-1)!0!}+\frac{c!}{(c-2)!1!}+...+\frac{c!}{0!(c-1)!}=c.\binom{c-1}{0}+c.\binom{c-1}{1}+...+c.\binom{c-1}{c-1}=c.2^{c-1}$.
+ Chúng ta tính ans(i) from the end.
Vì vậy, theo nguyên lý bù trừ ta có: $ans(i)=cnt(i).2^{cnt(i)-1}-ans(2i)-ans(3i)-...$.
Câu trả lời cho câu hỏi này là: $\sum\limits_{i=2}^{1000000}i.ans(i)$.
Độ phức tạp của thuật toán là: $O(k+\frac{k}{2}+\frac{k}{3}+...)=O(k.log(k))$.
Lời giải:

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

#define PB push_back
#define MP make_pair
#define L first
#define R second
#define sz(x) ((int)(x).size())
#define smax(x, y) ((x) = max((x), (y)))
#define smin(x, y) ((x) = min((x), (y)))
#define all(x) x.begin(),x.end()

const int maxn = 1e6 + 10;
const LL Mod = 1e9 + 7;
bool isp[maxn];
int sign[maxn],
 cnt[maxn];
LL P[maxn];
int n;

LL func(int x) {
 return (x * P[x - 1]) % Mod;
}

int main(){
 ios_base::sync_with_stdio(false);
 cin.tie(0);
 memset(isp, true, sizeof isp);
 fill(sign, sign + maxn, 1);
 isp[0] = isp[1] = false;
 for (int i = 2; i < maxn; i++)
  if (isp[i])
   for (int j = i; j < maxn; j += i) {
    isp[j] = i == j;
    if ((j / i) % i == 0)
     sign[j] = 0;
    else
     sign[j] *= -1;
   }
 P[0] = 1;
 for (int i = 1; i < maxn; i++)
  P[i] = (P[i - 1] << 1) % Mod;
 cin >> n;
 for (int x, i = 0; i < n; i++)
  cin >> x, cnt[x]++;
 for (int i = 1; i < maxn; i++)
  for (int j = i + i; j < maxn; j += i)
   cnt[i] += cnt[j];
 LL ans = 0;
 for (int i = 2; i < maxn; i++) {
  LL rc = 0;
  for (int j = i; j < maxn; j += i)
   rc = (rc + sign[j / i] * func(cnt[j])) % Mod;
  ans += rc * i;
  ans %= Mod;
 }
 ans = (ans + Mod) % Mod;
 cout << ans << endl;
 return 0;
}