結果

問題 No.312 置換処理
コンテスト
ユーザー itezpace
提出日時 2016-09-09 09:44:07
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 1,111 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,328 ms
コンパイル使用メモリ 171,156 KB
実行使用メモリ 12,392 KB
最終ジャッジ日時 2026-03-08 16:07:10
合計ジャッジ時間 2,666 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

vector<ll> eratosthenes(ll m){
  vector<ll> primes(m+1);
  for(ll i=2; i<m+1; ++i){
    primes[i]=i;
  }
  for(ll i=2; i*i<m+1; ++i){
    if(primes[i]){
      for(ll j=i*i; j<m+1; j+=i){
        primes[j]=0;
      }
    }
  }
  return primes;
}

int main(){
  ll n,x;
  cin>>n;
  ll m=sqrt(n)+1;
  vector<ll> v=eratosthenes(m);
  vector<ll> v2;
  for(ll i=0; i<m; ++i){
    if(v[i]) v2.push_back(v[i]);
  }
  vector<ll> v3;
  for(ll i=0; i<v2.size(); ++i){
    ll a=v2[i];
    while(1){
      if(n%a==0){
        n/=a;
        v3.push_back(a);
      } else {
        break;
      }
    }
  }
  if(v3.size()==0){
    x=n;
  } else {
    ll c=0;
    ll c2=0;
    for(ll i=0; i<v3.size(); ++i){
      if(v3[i]==2){
        c+=1;
      } else if(v3[i]==3){
        c2+=1;
      } else {
        break;
      }
    }
    if(c>=2){
      if(c2==0) x=4;
      else x=3;
    } else if(c==1){
      if(v3.size()>1) x=v3[1];
      else x=n;
    } else if(c==0){
      x=v3[0];
    }
  }
  cout<<x<<endl;
  return 0;
}
0