Codeforces 851 D. Arpa and a list of numbers

問題文
http://codeforces.com/contest/851/problem/D

問題文で与えられたが数直線上にあることを考える

区間ごとに分けることを考えてという関数を定義する。もし、全体の最大公約数がとしたいなら、答えはがより大きい時のの最小値の和。

それぞれの区間でのをもとめる、ある数(例えば)が区間に含まれる時、かかるコストはそれをで消すか、で割れるまで足していった時なので

になる。
次にの取る値について考える。

本題に入る前に二つの関数を定義する

: となるの個数を返す関数。この関数を計算するために配列を定義する。はからまでに含まれるの個数。この配列を用いるとと書ける
: を返す関数。この関数を計算するために配列を定義する。はからまでに含まれるの総和。この配列を用いるととかける。

さて、それぞれのの倍数の時についてでのコストを計算して足し上げていく。
つまり、その範囲を二つの区間に分割する]と]に分割するようなもっともよいを見つけ、一つ目の区間(図の青線部分)の数を削除し、二つ目の区間(図の赤線部分)の数をになるまで足し上げていけばよい。
求めるは　もし、との差がを超えるならで消すほうがコストが安いので

よって

時間計算量は

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2000000 + 10;
const long long INF = 1e18;

int n;
long long x, y;
long long b[N];
long long ps[N];

long long cnt(long long l,long long r){
  return b[r]-b[l-1];
}
long long sum(long long l,long long r){
  return ps[r]-ps[l-1];
}

void solve()
{
    cin >> n >> x >> y;
    for(int i = 0; i < n; ++ i) {
        int t;
        scanf("%d", &t);
        b[t] ++;
        ps[t] += t;
    }
    long long ans = INF;
    long long c = x / y;

    for(int i = 1; i < N; ++ i) {
        b[i] += b[i - 1];
        ps[i] += ps[i - 1];
    }

    for(long long g = 2; g <=1000000; g++) {
        long long tmp_ans = 0;
        long long f=min(g,(x+y-1)/y);
        for(long long k = g; k <= 1000000+g; k += g) {
          tmp_ans+=cnt(k-g+1,k-f)*x;
          tmp_ans+=(cnt(k-f+1,k)*k-sum(k-f+1,k))*y;
        }
        ans = min(ans, tmp_ans);
    }
    cout << ans << endl;

}

int main()
{
	solve();
	return 0;
}