結果

問題 No.811 約数の個数の最大化
コンテスト
ユーザー to10to10to10to
提出日時 2019-04-13 18:58:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 1,124 bytes
コンパイル時間 1,569 ms
コンパイル使用メモリ 169,172 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 11:18:06
合計ジャッジ時間 2,367 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:67:11: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized]
   67 |   cout << ans << endl;
      |           ^~~
main.cpp:53:16: note: 'ans' was declared here
   53 |   int n,k,ma=0,ans;
      |                ^~~

ソースコード

diff # 

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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define PI (acos(-1))

vector<int> divisor(int n){
  vector<int> div;
  for(int i=1; i*i<=n; i++){
    if(n%i==0){
      div.push_back(i);
      if(i*i!=n){
        div.push_back(n/i);
      }
    }
  }
  return div;
}

int prime_factorize(int n){//nの素因数の数
  int tmp = n,cnt=0;
  if(n==1)return 0;
  for(int p=2; p<=tmp; p++){
    if(n%p!=0)continue;
    while(n%p==0){
      cnt++;
      n/=p;
    }
  }
  if(n!=1)return 1;
  return cnt;
}

int gcd(int a,int b){
  if(a<b){
    swap(a,b);
  }
  int r;
  while(b>0){
    r = a%b;
    a = b;
    b = r;
  }
  return a;
}

int main(){
  int n,k,ma=0,ans;
  cin >> n >> k;
  reps(i,1,n){
    int g = gcd(i,n);
    int p = prime_factorize(g);
    //cout << i << " " << g << " " << p << endl;
    if(p >= k){
      int d = divisor(i).size();
      if(d > ma){
        ma = d;
        ans = i;
      }
    }
  }
  cout << ans << endl;
}
0