結果

問題 No.2449 square_permutation
ユーザー Wiiiiam104
提出日時 2023-08-31 21:28:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 961 ms / 2,000 ms
コード長 5,891 bytes
コンパイル時間 3,748 ms
コンパイル使用メモリ 223,888 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2025-01-03 04:54:04
合計ジャッジ時間 18,184 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#if __INCLUDE_LEVEL__
#include <bits/stdc++.h>
#include <atcoder/all>
#define int long long
#endif
#if !__INCLUDE_LEVEL__
#include __FILE__

//using mint=atcoder::static_modint<998244353>;
//using mint=modint; atcoder::modint::set_mod(int m);
//using vm=vector<mint>; using vvm=vector<vm>; using vvvm=vector<vvm>;
//cout<<fixed<<setprecision(10);

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  //your code here!
  int N;cin>>N;
  vi used(N+1,false);
  rep(i,N){
    int m=i+1;
    for(int j=2;j*j<=m;j++) if(m%(j*j)==0){m/=j*j;j--;}
    int res=m;
    for(int j=1;j*j<=N;j++) if(m*j*j<=N && !used[m*j*j]) res=m*j*j;
    used[res]=true; cout<<res<<(i!=N-1?' ':'\n');
  }
  return 0;
  
}


#else //template
using namespace std;

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vvvi = vector<vvi>;
using vs = vector<string>;
using pii = pair<int,int>;
using vpii = vector<pii>;


#define rep(i,n) for(int i=0;(i)<(int)(n);(i)++)
#define REPD(i,n) for(int i=(int)(n)-1;(i)>=0;(i)--)
#define FOR(i,a,n) for(int i=(a);(i)<(int)(n);(i)++)
#define FORD(i,a,n) for(int i=(int)(n)-1;(i)>=(int)(a);(i)--)
#define fore(x,vec) for(auto &x:(vec))

template<typename T> inline T chmax(T &a,const T &b){if(a<b)a=b;return a;}
template<typename T> inline T chmin(T &a,const T &b){if(b<a)a=b;return a;}

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
const vi dx={1,0,-1,0};
const vi dy={0,1,0,-1};
constexpr double pi=3.141592653589793;
constexpr double PI=3.141592653589793;

#define ALL(vec) (vec).begin(),(vec).end()
#define SORT(vec) sort(ALL((vec)))
#define LB(vec,x) (lower_bound(ALL(vec),(x))-(vec).begin())
#define ANS(res) {cout<<res<<endl;return 0;}
#define YESNO(b) {cout<<((bool)(b)?"Yes\n":"No\n");return 0;}
#define YES YESNO(1);
#define NO YESNO(0);
#define ERROR(s) {cout<<"Error: "<<s<<endl;exit(0);}

template<typename T> ostream &operator<<(ostream &os,const vector<T> &vec){
  for(int i=0;i<(int)vec.size();i++){os<<vec[i]<<(i+1!=vec.size()?" ":"");}return os;
}
template<typename T> istream &operator>>(istream& is,vector<T>& vec){
  for(int i=0;i<(int)vec.size();i++){is>>vec[i];}return is;
}


template<typename T> inline bool isPrime(T &a){
  if(a<2){return 0;}for(T i=2;i*i<=a;i++){if(a%i==0)return 0;}return 1;
}

//エラトステネスの篩
template<typename T> vector<bool> primes(T& N) {
  vector<bool> isprime(N+1,true);isprime[0]=isprime[1]=false;
  for(T p=2;p<N+1;p++){
    if(!isprime[p])continue;
    for(T q=p*2;q<=N;q+=p){isprime[q]=false;}
  }
  return isprime;
}

// ミラーラビン法 ここから
// A^N mod M
template<class T> T pow_mod(T A, T N, T M) {
  T res = 1 % M;
  A %= M;
  while (N) {
    if (N & 1) res = (res * A) % M;
    A = (A * A) % M;
    N >>= 1;
  }
  return res;
}

bool MillerRabin(long long N, vector<long long> A) {
  long long s = 0, d = N - 1;
  while (d % 2 == 0) {
    ++s;
    d >>= 1;
  }
  for (auto a : A) {
    if (N <= a) return true;
    long long t, x = pow_mod<__int128_t>(a, d, N);
    if (x != 1) {
      for (t = 0; t < s; ++t) {
        if (x == N - 1) break;
        x = __int128_t(x) * x % N;
      }
      if (t == s) return false;
    }
  }
  return true;
}

bool is_prime(long long N) {
  if (N <= 1) return false;
  if (N == 2) return true;
  if (N % 2 == 0) return false;
  if (N < 4759123141LL)
    return MillerRabin(N, {2, 7, 61});
  else
    return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
// ミラーラビン法 ここまで

//素因数分解
vpii prime_factories(int N){
  vpii res;
  for(int a=2;a*a<=N;a++){
    if(N%a!=0)continue;
    int ex=0;
    while(N%a==0){
      ex++;
      N/=a;
    }
    res.pb({a,ex});
  }
  if(N!=1)res.pb({N,1});
  return res;
}

// 二分探索:
// !f(v[i-1]) && f(v[i]) となるようなiのうちいずれか1つを返すか、
// 存在しないとき f(v[0]) なら 0, !f(v[0]) なら v.size() を返す
// 制約 : f(v[0]) ⇒ f(v[v.size()-1])
template<typename T>
int binarySearch(vector<T>& v, function<bool(T)> f){
  int min=-1, max=v.size();
  for(;max-min>1;){
    int mid=(min+max)/2;
    if(f(v[mid])) max=mid;
    else min=mid;
  }
  return max;
}
// 二分探索:
// !f(i-1) && f(i) となるようなiのうちいずれか1つを返すか、
// 存在しないとき f(0) なら 0, !f(0) なら N を返す
// 制約 : f(0) ⇒ f(N)
int binarySearch(int N, function<bool(int)> f){
  int min=-1, max=N;
  for(;max-min>1;){
    int mid=(min+max)/2;
    if(f(mid)) max=mid;
    else min=mid;
  }
  return max;
}


// 正確な比較が可能な分数
template<typename T> class fraction{
public:
  // 分母, 分子
  T top, bottom;
  fraction(T top_,T bottom_){top=top_;bottom=bottom_;if(bottom==0) ERROR("fraction<int> constractor: 0-devided error");}
  friend bool operator<(fraction const& a,fraction const& b){
    if(a.bottom>0!=b.bottom>0) return (ll)a.top*(ll)b.bottom<(ll)b.top*(ll)a.bottom;
    else return (ll)a.top*(ll)b.bottom>(ll)b.top*(ll)a.bottom;
  }
  friend bool operator>(fraction const& a,fraction const& b){
    if(a.bottom>0!=b.bottom>0) return (ll)a.top*(ll)b.bottom>(ll)b.top*(ll)a.bottom;
    else return (ll)a.top*(ll)b.bottom<(ll)b.top*(ll)a.bottom;
  }
  friend bool operator!=(fraction const& a,fraction const& b){return a>b||a<b;}
  friend bool operator>=(fraction const& a,fraction const& b){return a>b||a==b;}
  friend bool operator<=(fraction const& a,fraction const& b){return a<b||a==b;}
  friend bool operator==(fraction const& a,fraction const& b){return !(a!=b);}
};


//template ends here
//main() is at the top of this file
#endif
0