結果

問題 No.1611 Minimum Multiple with Double Divisors
コンテスト
ユーザー akua
提出日時 2022-09-20 02:02:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,924 bytes
コンパイル時間 1,374 ms
コンパイル使用メモリ 119,756 KB
最終ジャッジ日時 2025-02-07 12:41:42
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#include <atcoder/all>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;  
//using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
typedef long long ll;
typedef unsigned long long ull;
const ll inf=1e18;  
using graph = vector<vector<int> > ;
using P= pair<ll,ll>;  
using vi=vector<int>;
using vvi=vector<vi>;
using vll=vector<ll>; 
using vvll=vector<vll>;
using vp=vector<P>;
using vpp=vector<vp>;
//string T="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//string S="abcdefghijklmnopqrstuvwxyz";
//g++ main.cpp -std=c++14 -I .  
//cout <<setprecision(20);
//cout << fixed << setprecision(10);
//cin.tie(0); ios::sync_with_stdio(false);
const double PI = acos(-1);
 
int vx[]={0,1,0,-1,-1,1,1,-1},vy[]={1,0,-1,0,1,1,-1,-1};
 
ll pow_pow(ll x,ll n,ll mod){
    if(n==0) return 1; 
    x%=mod;
    ll res=pow_pow(x*x%mod,n/2,mod);
    if(n&1)res=res*x%mod;
    return res;
}
ll extgcd(ll a,ll b,ll &x,ll &y){
  ll d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }
  else{
    x=1;y=0;
  }
  return d;
}
ll mod_inverse(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
 
int gcd(int x,int y){
    if(y==0)return x;
    return gcd(y,x%y);
}
 
ll lcm(ll x,ll y){
    return ll(x/gcd(x,y))*y;
}
template<class T> bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    else return false;
}
template<class T> bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    else return false;
}

const int N=55555;
int isprime[N+1];
vi prime;
void getPrime(){
  rep(i,N+1)isprime[i]=1;
  isprime[0]=0;isprime[1]=0;
  for(int i=2; i<=N; i++){
    if(isprime[i])prime.push_back(i);
    for(int j=2*i; j<=N; j+=i){
      isprime[j]=0;
    }
  }
}
int main(){cin.tie(0); ios::sync_with_stdio(false);
  getPrime();
  int t; cin >> t;
  vll anss;
  rep(test,t){
    ll x; cin >> x;
    ll y=x;
    ll now=x;
    ll ans=inf;
    for(auto u:prime){
      if(x%u){chmin(ans,u*1ll);break;}
      else {
        int cnt=0;
        while(now%u==0){
          now/=u;
          cnt++;
        }
        chmin(ans,pow_pow(u,cnt+1,inf));
      }
    }
    ans*=x;
    anss.push_back(ans);
  } 
  for(auto u:anss)cout << u << endl;
}
0