GCDEX — GCD Extreme

Заявление

Учитывая значение N, вам нужно будет найти значение G. Значение G дано в следующем коде.

G = 0;
for (i = 1; i < N; i++)
  for (j = i+1; j <= N; j++) 
    G += gcd(i, j);

Здесь gcd() — это функция, которая находит наибольший общий делитель двух входных чисел.

Первое решение

По функции Мёбиуса:

Временная сложность: O(Q nlog(n))

Оптимизация 1
Определите набор возможных значений N/k:

Итак, можно перебрать S:

Оптимизация 2
Создайте массив с накоплением суммы функции Мебиуса:

Теперь можно перебирать возможные значения (N/k)/d, аналогично оптимизации 1, создавать все возможные значения S[i]/d, перебирать их и умножать на накопленную сумму мёбиуса.

Временная сложность: O(Q n)

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
using ll = long long;
#define FIFO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int lpf[N];
void sieve(){
 for(int i=2; i<N; i++){
  if(!lpf[i]){
   lpf[i] = i;
   for(ll j=1LL*i*i; j<N; j+=i){
    if(lpf[j] == 0) lpf[j] = i;
   }
  }
 }
}
int mobius[N];
int s_mobius[N];
void cmob(){
 mobius[1] = 1;
 for(int i=2; i<N; i++){
  if(lpf[i] == i) mobius[i] = -1;
  else{
   if(lpf[i/lpf[i]] == lpf[i]) mobius[i] = 0;
   else mobius[i] = -1*mobius[i/lpf[i]];
  }
 }
 for(int i=1; i<N; i++)
  s_mobius[i] = s_mobius[i-1] + mobius[i];
}

void fill(int n, vector <int> &values, vector <pair <int,int> > &range){
 for(int i=1; 1LL*i*i<=n; i++){
  values.push_back(i);
  range.push_back({n/i, n/(i+1)+1});
 }
 int last = range[range.size()-1].second;
 while(last > 1){
  last--;
  values.push_back(n/last);
  range.push_back({last, last});
 }
}

int main(){
 sieve();
 cmob();
 int n;
 while(true){
  cin >> n; if(n == 0) break;
  ll ans = 0; vector <int> values;
  vector <pair <int,int> > range;
  fill(n, values, range);

  for(int i=0; i<values.size(); i++){
   int v = values[i];
   ll aux = 0;
   vector <int> n_v; vector <pair <int,int> > n_r;
   fill(v, n_v,n_r);
   for(int j=0; j<n_v.size(); j++){
    int k = n_v[j];
    ll s =  1LL*k*k-(1LL*k*(k+1))/2;
    aux += s*(s_mobius[n_r[j].first] - s_mobius[n_r[j].second-1]);
   }
   ll s = (1LL*range[i].first*(range[i].first+1))/2;
   s -= (1LL*range[i].second*(range[i].second-1))/2;
   ans += aux*s;
  }
  cout << ans << '\n';
 }
 return 0;
}

Второе решение

Определите массив динамического программирования с помощью этой концепции:

Временная сложность: O(n^(4/3) + Q)

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
using ll = long long;
#define FIFO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int lpf[N];
void sieve(){
 for(int i=2; i<N; i++){
  if(!lpf[i]){
   lpf[i] = i;
   for(ll j=1LL*i*i; j<N; j+=i){
    if(lpf[j] == 0) lpf[j] = i;
   }
  }
 }
}
int phi[N];
void cphi(){
 phi[1] = 1;
 for(int i=2; i<N; i++){
  if(!phi[i]){
   phi[i] = i-1;
   for(ll j=2*i; j<N; j+=i){
    if(phi[j] == 0) phi[j] = j;
    phi[j] = phi[j]/i*(i-1);
   }
  }
 }
}

void generate_divisors(int n, int index, int d, vector<pair <int,int> > &factorization, vector <int> &ans){ 
 if(1LL*d*d > n) return;
 
 if(index == factorization.size()){
  ans.push_back(d);
  if(d*d != n) ans.push_back(n/d); 
  return;
 }
 for(int i = 0; i <= factorization[index].second; ++i){
  generate_divisors(n, index+1, d, factorization, ans); 
  d *= factorization[index].first;
 }
}

ll DP[N];
void solve(){
 DP[1] = 0; DP[2] = 1;
 for(int i=2; i<N-1; i++){
  DP[i+1] = DP[i] - (i+1);
  vector <pair <int,int> > f;
  int aux = i+1;
  while(aux > 1){
   int d = lpf[aux];
   f.push_back({d,0});
   while(aux%d == 0){
    f[f.size()-1].second++;
    aux /= d;
   }
  }
  vector <int> divisors;
  generate_divisors(i+1, 0, 1, f, divisors);
  for(int j=0; j<divisors.size(); j++){
   DP[i+1] += 1LL*((i+1)/divisors[j])*phi[divisors[j]];
  }
 }
}

int main(){
 FIFO;
 sieve();
 cphi();
 solve();
 int n;
 while(true){
  cin >> n; if(n == 0) break;
  cout << DP[n] << '\n';
 }
 return 0;
}