[yukicoder] No. 811 約数の個数の最大化

2019年6月27日2019年6月28日

問題

方針

約数の個数

\( i \) の約数の個数を \( d_i \) とします。\( i = nk \ (1\leq n \leq N \wedge 1 \leq k \leq N)\) を満たす \( i \) について、インクリメントさせます。

約数の個数のコード

  int dp[N]{};
  for (int i = 0; i < N; i++) dp[i] = 1;

  for (int i = 2; i < N; i++) {
    for (int j = i; j < N; j += i) {
      dp[j]++;
    }
  }

素因数の個数

\( i \) の素因数の個数を \( g_i \) とすると、\( g_{ij} = g_{i} + g_{j} \) が成り立ちます。これを利用して求めます。

素因数の個数を求めるコード

  int dp2[N]{};
  for (int i = 2; i < N; i++) {
    dp2[i] = 1;
  }
  for (int i = 2; i * i < N; i++) {
    for (int j = 2; i * j < N; j++) {
      dp2[i * j] = dp2[i] + dp2[j];
    }
  }

共通の素因数の個数

\( a \) と \( b \) の共通の素因数の個数は、\( a \) と \( b \) の最大公約数の素因数の個数になります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAX = 100001;

int gcd(int m, int n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  
  int m = sqrt(N);
  int dp[N]{};
  for (int i = 0; i < N; i++) dp[i] = 1;

  for (int i = 2; i < N; i++) {
    for (int j = i; j < N; j += i) {
      dp[j]++;
    }
  }

  int dp2[N]{};
  for (int i = 2; i < N; i++) {
    dp2[i] = 1;
  }
  for (int i = 2; i * i < N; i++) {
    for (int j = 2; i * j < N; j++) {
      dp2[i * j] = dp2[i] + dp2[j];
    }
  }

  int ans = 1;
  int maxV = 0;
  for (int i = 1; i < N; i++) {
    int g = gcd(N, i);
    if (maxV < dp[i] && K <= dp2[g]) {
      maxV = dp[i];
      ans = i;
    }
  }

  cout << ans << "\n";
  return 0;
}